home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume10 / cbw / part05 / eclass.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-06-17  |  9.0 KB  |  477 lines
  1. /*
  2.  * Equivalence class information about a cipher block.
  3.  *
  4.  * Bob Baldwin, January 1985.
  5.  */
  6.  
  7. #include    <stdio.h>
  8. #include    <math.h>
  9. #include    "window.h"
  10. #include    "terminal.h"
  11. #include    "layout.h"
  12. #include    "specs.h"
  13. #include    "cipher.h"
  14.  
  15.  
  16. #define    DEBUG    FALSE
  17.  
  18. #define    MIN_SHOW_SCORE    (0.7)
  19. #define    ECBLABEL1    "Equiv class guessing at level %6.3f  -- Please Wait"
  20. #define    ECBLABEL2    "Equiv class guessing at level %6.3f  -- Done"
  21. #define    ECBHELP "F3 enters guess, ^G undoes it."
  22.  
  23.  
  24. extern    char    mcbuf[];
  25. extern    ecinfo    gecinfo;
  26. extern    ecbdraw(), ecbfirst(), ecbenter(), ecbundo();
  27.  
  28. /* Gloabal State. */
  29. float    ec_accept_level = 0.0;
  30. keyer    ecbktab[] = {
  31.         {CACCEPT, ecbenter},
  32.         {CUNDO, ecbundo},
  33.         {CGO_UP, jogup},
  34.         {CGO_DOWN, jogdown},
  35.         {CGO_LEFT, jogleft},
  36.         {CGO_RIGHT, jogright},
  37.         {0, NULL},
  38. };
  39.  
  40.  
  41. /* Routine invoked by user to put up the equivalence class
  42.  * guessing window.
  43.  * The window is drawn empty, and then filled in with the guess.
  44.  * Return NULL if command completes ok.
  45.  */
  46. char    *ecbguess(str)
  47. char    *str;            /* Command line */
  48. {
  49.     ecinfo    *ecbi;
  50.     int        i;
  51.     gwindow    *ecb;
  52.  
  53.     ecb = &gbstore;
  54.     ecbi = &gecinfo;
  55.     ec_init(mcbuf, refperm(dbsgetblk(&dbstore)), ecbi);
  56.  
  57.     if ((i = sscanf(str, "%*[^:]: %f", &ec_accept_level)) != 1)  {
  58.         return("Could not parse acceptance level.");
  59.         }
  60.  
  61.     gbsswitch(ecb, ((char *) ecbi), ecbktab, ecbfirst, wl_noop, ecbdraw);
  62.  
  63.     sprintf(statmsg, ECBLABEL1, ec_accept_level);
  64.     gblset(&gblabel, statmsg);
  65.  
  66.     ecbdraw(ecb);
  67.     fflush(stdout);
  68.  
  69.     ec_autoguess(ecbi, ec_accept_level);
  70.     decode(ecbi->ciphertext, ecbi->plaintext, ecbi->perm);
  71.  
  72.     sprintf(statmsg, ECBLABEL2, ec_accept_level);
  73.     gblset(&gblabel, statmsg);
  74.     ecbdraw(ecb);
  75.  
  76.     return(NULL);
  77. }
  78.  
  79.  
  80. /*  (re) Draw the window.
  81.  */
  82. ecbdraw(ecb)
  83. gwindow    *ecb;
  84. {
  85.     int            i;
  86.     int            row, col;
  87.     ecinfo        *ecbi;
  88.  
  89.     ecbi = ((ecinfo *) ecb->wprivate);
  90.     row = 1;
  91.     col = 1;
  92.  
  93.     for (i = 0 ; i < BLOCKSIZE ; i++)  {
  94.         if (i%LINELEN == 0) {
  95.             wl_setcur(ecb, gbspos2row(i), gbspos2col(i));
  96.             }
  97.         plnchars(1, char2sym(ecbi->plaintext[i]));
  98.         }
  99.  
  100.     for (i = gbspos2row(BLOCKSIZE) ; i <= GBHEIGHT ; i++) {
  101.         wl_setcur(ecb, i, 1);
  102.         plnchars(LINELEN, ' ');
  103.         }
  104.  
  105.     for (i = 1 ; i <= GBHEIGHT ; i++) {
  106.         wl_setcur(ecb, i, LINELEN+1);
  107.         plnchars(ecb->wwidth - LINELEN, ' ');
  108.         }
  109.  
  110.     wl_setcur(ecb, row, col);
  111. }
  112.  
  113.  
  114. /* First time cursor enters window.
  115.  */
  116. ecbfirst(ecb, row, col)
  117. gwindow    *ecb;
  118. int            row, col;
  119. {
  120.     usrhelp(&user, ECBHELP);
  121.     wl_setcur(ecb, row, col);
  122. }
  123.  
  124.  
  125. /* Enter the guess into the decryption block.
  126.  */
  127. ecbenter(ecb)
  128. gwindow    *ecb;
  129. {
  130.     ecinfo        *ecbi;
  131.  
  132.     ecbi = ((ecinfo *) ecb->wprivate);
  133.     dbsmerge(&dbstore, ecbi->perm);
  134.     wl_rcursor(ecb);
  135. }
  136.  
  137.  
  138. /* Undo the last guess.
  139.  */
  140. ecbundo(ecb)
  141. gwindow    *ecb;
  142. {
  143.     ecinfo        *ecbi;
  144.  
  145.     ecbi = ((ecinfo *) ecb->wprivate);
  146.     dbsundo(&dbstore);
  147.     wl_rcursor(ecb);
  148. }
  149.  
  150.  
  151.  
  152.  
  153. /* Dump plaintext chars onto stream.
  154.  */
  155. ec_dplain(out, eci)
  156. FILE    *out;
  157. ecinfo    *eci;
  158. {
  159.     int        i,c;
  160.     int        *pbuf;
  161.  
  162.     pbuf = &eci->plaintext[0];
  163.     for (i = 0 ; i < BLOCKSIZE ; i++) {
  164.         c = *pbuf++;
  165.         if (i % 20 == 0)  fprintf(out,"\n");
  166.         if (c != NONE)
  167.             write_char(out, c);
  168.         else
  169.             write_char(out, '.');
  170.         }
  171.     fprintf(out,"\n");
  172. }
  173.  
  174.  
  175. /* Dump shifted cipher chars onto stream.
  176.  */
  177. ec_dscipher(out, eci)
  178. FILE    *out;
  179. ecinfo    *eci;
  180. {
  181.     int        i,c;
  182.     int        *pbuf;
  183.  
  184.     pbuf = &eci->scipher[0];
  185.     for (i = 0 ; i < BLOCKSIZE ; i++) {
  186.         c = *pbuf++;
  187.         if (i++ % 20 == 0)  fprintf(out,"\n");
  188.         if (c != NONE)
  189.             write_char(out, c);
  190.         else
  191.             write_char(out, '.');
  192.         }
  193.     fprintf(out,"\n");
  194. }
  195.  
  196.  
  197. /* Dump table of next pointers onto a stream.
  198.  */
  199. ec_dnext(out, eci)
  200. FILE    *out;
  201. ecinfo    *eci;
  202. {
  203.     writeperm(out, &(eci->next[0]));
  204. }
  205.  
  206.  
  207. /* Dump size table onto a stream.
  208.  */
  209. ec_dsizetab(out, eci)
  210. FILE    *out;
  211. ecinfo    *eci;
  212. {
  213.     int        i;
  214.  
  215.     fprintf(out, "\nThere are %d classes longer than 1 character.\n",
  216.             eci->sizelast);
  217.     for (i = 0 ; i < eci->sizelast ; i++)  {
  218.         fprintf(out, "Size: %d,  First member: %d.\n",
  219.                 eci->sizelist[i].size, eci->sizelist[i].firstpos);
  220.         }
  221. }
  222.  
  223.  
  224. /* Dump our permutation onto a stream.
  225.  */
  226. ec_dperm(out, eci)
  227. FILE    *out;
  228. ecinfo    *eci;
  229. {
  230.     writeperm(out, &(eci->perm[0]));
  231. }
  232.  
  233.  
  234. /* Dump the permutation map onto a stream.
  235.  */
  236. ec_dpmap(out, eci)
  237. FILE    *out;
  238. ecinfo    *eci;
  239. {
  240.     writeperm(out, &(eci->permmap[0]));
  241. }
  242.  
  243.  
  244.  
  245. /* Update ecbi to reflect the automatic guesses.
  246.  */
  247. ec_autoguess(ecbi, alevel)
  248. ecinfo    *ecbi;
  249. float    alevel;
  250. {    int        i, c;
  251.     int        classpos;
  252.     int        x, y;
  253.  
  254.     for (i = 0 ; i < ecbi->sizelast ; i++)  {
  255.         classpos = ecbi->sizelist[i].firstpos;
  256.         c = ec_best(ecbi, classpos, alevel);
  257.         if (c != NONE) {
  258.             x = ecbi->scipher[classpos];
  259.             y = MODMASK & (c + classpos);
  260.             if (!perm_conflict(ecbi->perm, x, y)) {
  261.                 ecbi->perm[x] = y;
  262.                 ecbi->perm[y] = x;
  263.                 }
  264. #if DEBUG
  265.             else {
  266.                 printf("ec_autoguess: Best guess conflicts");
  267.                 printf(" with an accepted.\n");
  268.                 }
  269. #endif
  270.             }
  271.         }
  272. }
  273.  
  274.  
  275. /* Score a single equivalence class.
  276.  * Bigger scores are better scores.  They range from 0 to 1.
  277.  * A score of zero means the choice is not possible.
  278.  */
  279. float    ec_cscore(eci, firstpos, plainchar)
  280. ecinfo    *eci;
  281. int        firstpos;
  282. int        plainchar;
  283. {
  284.     extern    float    logvar;
  285.     float    score;
  286.     int        pvec[BLOCKSIZE+1];
  287.     int        ccount;
  288.     char    str[BLOCKSIZE+1];
  289.  
  290.  
  291.     if (decode_class(eci, firstpos, plainchar, pvec) == ERROR)  {
  292.         return(0.0);
  293.         }
  294.  
  295.     score = pvec_1score(pvec);
  296.     if (score < 0.0)  return(0.0);
  297.     score = exp(-(score * score) / 2.0);
  298.     for (ccount = 0 ; pvec[ccount] != NONE ; ccount++);
  299.     score = score / sqrt(2*PI*logvar/ccount);
  300.  
  301. #if DEBUG
  302.     if (score > MIN_SHOW_SCORE) {
  303.         pvec2str(str, pvec);
  304.         printf("Derived characters are '%s", str);
  305.         printf("', their score is %7.4f\n", score);
  306.         }
  307. #endif
  308.     return(score);
  309. }
  310.  
  311.  
  312. /* Select best plaintext value for a ciphertext equiv class.
  313.  * The class is identified by the position in the block of one
  314.  * of the characters in the class.  The plaintext value for
  315.  * an entire class can be specified by the plaintext value of
  316.  * one of its members.  This routine returns the best plaintext
  317.  * value for the ciphertext character at position firstpos.
  318.  * If there is not a clear best value, NONE is returned.
  319.  */
  320. int    ec_best(eci, firstpos, alevel)
  321. ecinfo    *eci;
  322. int        firstpos;
  323. float    alevel;
  324. {
  325.     float    total_score, score;
  326.     float    best_score;
  327.     int        best_char;
  328.     int        c;
  329.     int        x,y;
  330.     float    count;
  331.  
  332. #if DEBUG
  333.     int        pvec[BLOCKSIZE+1];
  334.     char    str[BLOCKSIZE+1];
  335.  
  336.     printf("\n");
  337.     printf("The first position of this class is %d.\n", firstpos);
  338. #endif
  339.     total_score = 0.0;
  340.     best_score = 0.0;
  341.     count = 0.0;
  342.     best_char = NONE;
  343.  
  344.     for (c = 0 ; c <= MAXCHAR  ; c++)  {
  345.         score = ec_cscore(eci, firstpos, c);
  346.         if (score > 0.0)  {
  347.             count += 1.0;
  348.             total_score += score;
  349.             }
  350.         if (score > best_score) {
  351.             best_score = score;
  352.             best_char = c;
  353.             }
  354.         }
  355.  
  356. #if DEBUG
  357.     printf("Total score is %7.4f", total_score);
  358.     printf(".  Count is %4.0f.\n", count);
  359. #endif
  360.     if (total_score == 0.0  ||  count == 0.0  ||  best_char == NONE) {
  361. #if DEBUG
  362.         printf("NO GUESSES\n");
  363. #endif
  364.         return(NONE);
  365.         }
  366. #if DEBUG
  367.     printf("Best score is %7.4f", best_score);
  368.     printf(", which is %7.4f fraction of total", best_score/total_score);
  369.     printf(".\n");
  370.  
  371.     decode_class(eci, firstpos, best_char, pvec);
  372.     pvec2str(str, pvec);
  373.     printf("The best chars are '%s.\n", str);
  374. #endif
  375.  
  376.     if (best_score  >  alevel * (total_score - best_score)) {
  377.         return(best_char);
  378.         }
  379.     else {
  380.         return(NONE);
  381.         }
  382. }
  383.  
  384.  
  385. /* Fill in equiv class info from given ciphertext block
  386.  * and permutation.
  387.  */
  388. ec_init(cipher, perm, eci)
  389. char    cipher[];
  390. int        perm[];
  391. ecinfo    *eci;
  392. {
  393.     int        i,j;
  394.     int        lastmember;
  395.     int        firstpos, size;
  396.  
  397.     eci->sizelast = 0;
  398.     eci->sizemin = 2;
  399.     for (i = 0 ; i < BLOCKSIZE ; i++)  {
  400.         eci->ciphertext[i] = cipher[i];
  401.         eci->scipher[i] = (cipher[i] + i)&MODMASK;
  402.         eci->perm[i] = perm[i];
  403.         eci->permmap[i] = NONE;
  404.         }
  405.     decode(eci->ciphertext, eci->plaintext, eci->perm);
  406.  
  407.  
  408.     /* The permmap points to the most recent member we have seen */
  409.     /* of each known class, or a NONE.  Ptrs are array indexes. */
  410.     for (i = BLOCKSIZE-1 ; i >= 0 ; i--) {
  411.         eci->next[i] = i;
  412.         if ((lastmember = eci->permmap[eci->scipher[i]]) != NONE) {
  413.             eci->next[i] = eci->next[lastmember];
  414.             eci->next[lastmember] = i;
  415.             }
  416.         eci->permmap[eci->scipher[i]] = i;
  417.         }
  418.  
  419.     for (i = 0 ; i < BLOCKSIZE ; i++)  {
  420.         firstpos = eci->permmap[i];
  421.         if (firstpos != NONE)  {
  422.             size = ec_compsize(eci, firstpos);
  423.             ec_addsize(eci, size, firstpos);
  424.             }
  425.         }
  426. }
  427.  
  428.  
  429. /* Add an entry to the size list.
  430.  * Implementation:  Find the first slot before sizelast+1 that
  431.  * has a size less than the size arg.  Shuffle down the list
  432.  * to create a hole and insert the new entry.
  433.  */
  434. ec_addsize(eci, size, firstmember)
  435. register    ecinfo    *eci;
  436. int        size;
  437. int        firstmember;
  438. {
  439.     int        k;        /* Slot where new entry will go. */
  440.     int        i;
  441.     ecsize    sizeinfo;
  442.  
  443.     if (size < eci->sizemin) return;
  444.  
  445.     sizeinfo.size = size;
  446.     sizeinfo.firstpos = firstmember;
  447.     for (k = 0 ; k < eci->sizelast ; k++)  {
  448.         if (eci->sizelist[k].size < size)  break;
  449.         }
  450.     if (k >= SZMAX) return;
  451.  
  452.     for (i = eci->sizelast ; i > k ; i--)  {
  453.         eci->sizelist[i] = eci->sizelist[i-1];
  454.         }
  455.     eci->sizelast++;
  456.  
  457.     eci->sizelist[k] = sizeinfo;
  458. }
  459.  
  460.  
  461. /* Compute the size of a clas given a pointer to one of its members.
  462.  */
  463. int    ec_compsize(eci, member)
  464. ecinfo    *eci;
  465. int        member;
  466. {
  467.     int        size;
  468.     int        position;
  469.     int        firstflag;
  470.  
  471.     size = 0;
  472.     for_pos_in_class(position, member) {
  473.         size++;
  474.         }
  475.     return(size);
  476. }
  477.