Modules/rotormodule.c

   1 /***********************************************************
   2 Copyright 1994 by Lance Ellinghouse,
   3 Cathedral City, California Republic, United States of America.
   4
   5                         All Rights Reserved
   6
   7 Permission to use, copy, modify, and distribute this software and its
   8 documentation for any purpose and without fee is hereby granted,
   9 provided that the above copyright notice appear in all copies and that
  10 both that copyright notice and this permission notice appear in
  11 supporting documentation, and that the name of Lance Ellinghouse
  12 not be used in advertising or publicity pertaining to distribution
  13 of the software without specific, written prior permission.
  14
  15 LANCE ELLINGHOUSE DISCLAIMS ALL WARRANTIES WITH REGARD TO
  16 THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  17 FITNESS, IN NO EVENT SHALL LANCE ELLINGHOUSE BE LIABLE FOR ANY SPECIAL,
  18 INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING
  19 FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
  20 NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
  21 WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  22
  23 ******************************************************************/
  24
  25 /* This creates an encryption and decryption engine I am calling
  26    a rotor due to the original design was a harware rotor with
  27    contacts used in Germany during WWII.
  28
  29 Rotor Module:
  30
  31 -  rotor.newrotor('key') -> rotorobject  (default of 6 rotors)
  32 -  rotor.newrotor('key', num_rotors) -> rotorobject
  33
  34 Rotor Objects:
  35
  36 -  ro.setkey('string') -> None (resets the key as defined in newrotor().
  37 -  ro.encrypt('string') -> encrypted string
  38 -  ro.decrypt('encrypted string') -> unencrypted string
  39
  40 -  ro.encryptmore('string') -> encrypted string
  41 -  ro.decryptmore('encrypted string') -> unencrypted string
  42
  43 NOTE: the {en,de}cryptmore() methods use the setup that was
  44       established via the {en,de}crypt calls. They will NOT
  45       re-initalize the rotors unless: 1) They have not been
  46       initalized with {en,de}crypt since the last setkey() call;
  47       2) {en,de}crypt has not been called for this rotor yet.
  48
  49 NOTE: you MUST use the SAME key in rotor.newrotor()
  50       if you wish to decrypt an encrypted string.
  51       Also, the encrypted string is NOT 0-127 ASCII.
  52       It is considered BINARY data.
  53
  54 */
  55
  56 /* Rotor objects */
  57
  58 #include "Python.h"
  59 #include "mymath.h"
  60
  61 #ifndef TRUE
  62 #define TRUE    1
  63 #endif
  64 #ifndef FALSE
  65 #define FALSE   0
  66 #endif
  67
  68 typedef struct {
  69         PyObject_HEAD
  70         int seed[3];
  71         short key[5];
  72         int  isinited;
  73         int  size;
  74         int  size_mask;
  75         int  rotors;
  76         unsigned char *e_rotor;              /* [num_rotors][size] */
  77         unsigned char *d_rotor;              /* [num_rotors][size] */
  78         unsigned char *positions;            /* [num_rotors] */
  79         unsigned char *advances;             /* [num_rotors] */
  80 } Rotorobj;
  81
  82 staticforward PyTypeObject Rotor_Type;
  83
  84 #define is_rotor(v)             ((v)->ob_type == &Rotor_Type)
  85
  86 \f
  87 /* This defines the necessary routines to manage rotor objects */
  88
  89 static void
  90 set_seed(r)
  91         Rotorobj *r;
  92 {
  93         r->seed[0] = r->key[0];
  94         r->seed[1] = r->key[1];
  95         r->seed[2] = r->key[2];
  96         r->isinited = FALSE;
  97 }
  98
  99 /* Return the next random number in the range [0.0 .. 1.0) */
 100 static double
 101 r_random(r)
 102         Rotorobj *r;
 103 {
 104         int x, y, z;
 105         double val, term;
 106
 107         x = r->seed[0];
 108         y = r->seed[1];
 109         z = r->seed[2];
 110
 111         x = 171 * (x % 177) - 2 * (x/177);
 112         y = 172 * (y % 176) - 35 * (y/176);
 113         z = 170 * (z % 178) - 63 * (z/178);
 114
 115         if (x < 0) x = x + 30269;
 116         if (y < 0) y = y + 30307;
 117         if (z < 0) z = z + 30323;
 118
 119         r->seed[0] = x;
 120         r->seed[1] = y;
 121         r->seed[2] = z;
 122
 123         term = (double)(
 124                 (((double)x)/(double)30269.0) +
 125                 (((double)y)/(double)30307.0) +
 126                 (((double)z)/(double)30323.0)
 127                 );
 128         val = term - (double)floor((double)term);
 129
 130         if (val >= 1.0)
 131                 val = 0.0;
 132
 133         return val;
 134 }
 135
 136 static short
 137 r_rand(r, s)
 138         Rotorobj *r;
 139         short s;
 140 {
 141         return (short)((short)(r_random(r) * (double)s) % s);
 142 }
 143
 144 static void
 145 set_key(r, key)
 146         Rotorobj *r;
 147         char *key;
 148 {
 149         unsigned long k1=995, k2=576, k3=767, k4=671, k5=463;
 150         int i;
 151         int len = strlen(key);
 152
 153         for (i = 0; i < len; i++) {
 154                 unsigned short ki = Py_CHARMASK(key[i]);
 155
 156                 k1 = (((k1<<3 | k1>>13) + ki) & 65535);
 157                 k2 = (((k2<<3 | k2>>13) ^ ki) & 65535);
 158                 k3 = (((k3<<3 | k3>>13) - ki) & 65535);
 159                 k4 = ((ki - (k4<<3 | k4>>13)) & 65535);
 160                 k5 = (((k5<<3 | k5>>13) ^ ~ki) & 65535);
 161         }
 162         r->key[0] = (short)k1;
 163         r->key[1] = (short)(k2|1);
 164         r->key[2] = (short)k3;
 165         r->key[3] = (short)k4;
 166         r->key[4] = (short)k5;
 167
 168         set_seed(r);
 169 }
 170
 171
 172 \f
 173 /* These define the interface to a rotor object */
 174 static Rotorobj *
 175 rotorobj_new(num_rotors, key)
 176         int num_rotors;
 177         char *key;
 178 {
 179         Rotorobj *xp;
 180
 181         xp = PyObject_NEW(Rotorobj, &Rotor_Type);
 182         if (xp == NULL)
 183                 return NULL;
 184         set_key(xp, key);
 185
 186         xp->size = 256;
 187         xp->size_mask = xp->size - 1;
 188         xp->size_mask = 0;
 189         xp->rotors = num_rotors;
 190         xp->e_rotor = NULL;
 191         xp->d_rotor = NULL;
 192         xp->positions = NULL;
 193         xp->advances = NULL;
 194
 195         if (!(xp->e_rotor = PyMem_NEW(unsigned char, num_rotors * xp->size)))
 196                 goto finally;
 197         if (!(xp->d_rotor = PyMem_NEW(unsigned char, num_rotors * xp->size)))
 198                 goto finally;
 199         if (!(xp->positions = PyMem_NEW(unsigned char, num_rotors)))
 200                 goto finally;
 201         if (!(xp->advances = PyMem_NEW(unsigned char, num_rotors)))
 202                 goto finally;
 203
 204         return xp;
 205
 206   finally:
 207         PyMem_XDEL(xp->e_rotor);
 208         PyMem_XDEL(xp->d_rotor);
 209         PyMem_XDEL(xp->positions);
 210         PyMem_XDEL(xp->advances);
 211         Py_DECREF(xp);
 212         return (Rotorobj*)PyErr_NoMemory();
 213 }
 214
 215 \f
 216 /* These routines impliment the rotor itself */
 217
 218 /*  Here is a fairly sophisticated {en,de}cryption system.  It is based on
 219     the idea of a "rotor" machine.  A bunch of rotors, each with a
 220     different permutation of the alphabet, rotate around a different amount
 221     after encrypting one character.  The current state of the rotors is
 222     used to encrypt one character.
 223
 224     The code is smart enought to tell if your alphabet has a number of
 225     characters equal to a power of two.  If it does, it uses logical
 226     operations, if not it uses div and mod (both require a division).
 227
 228     You will need to make two changes to the code 1) convert to c, and
 229     customize for an alphabet of 255 chars 2) add a filter at the begining,
 230     and end, which subtracts one on the way in, and adds one on the way
 231     out.
 232
 233     You might wish to do some timing studies.  Another viable alternative
 234     is to "byte stuff" the encrypted data of a normal (perhaps this one)
 235     encryption routine.
 236
 237     j'
 238
 239  */
 240
 241 /* Note: the C code here is a fairly straightforward transliteration of a
 242  * rotor implemented in lisp.  The original lisp code has been removed from
 243  * this file to for simplification, but I've kept the docstrings as
 244  * comments in front of the functions.
 245  */
 246
 247
 248 /* Set ROTOR to the identity permutation */
 249 static void
 250 RTR_make_id_rotor(r, rtr)
 251         Rotorobj *r;
 252         unsigned char *rtr;
 253 {
 254         register int j;
 255         register int size = r->size;
 256         for (j = 0; j < size; j++) {
 257                 rtr[j] = (unsigned char)j;
 258         }
 259 }
 260
 261
 262 /* The current set of encryption rotors */
 263 static void
 264 RTR_e_rotors(r)
 265         Rotorobj *r;
 266 {
 267         int i;
 268         for (i = 0; i < r->rotors; i++) {
 269                 RTR_make_id_rotor(r, &(r->e_rotor[(i*r->size)]));
 270         }
 271 }
 272
 273 /* The current set of decryption rotors */
 274 static void
 275 RTR_d_rotors(r)
 276         Rotorobj *r;
 277 {
 278         register int i, j;
 279         for (i = 0; i < r->rotors; i++) {
 280                 for (j = 0; j < r->size; j++) {
 281                         r->d_rotor[((i*r->size)+j)] = (unsigned char)j;
 282                 }
 283         }
 284 }
 285
 286 /* The positions of the rotors at this time */
 287 static void
 288 RTR_positions(r)
 289         Rotorobj *r;
 290 {
 291         int i;
 292         for (i = 0; i < r->rotors; i++) {
 293                 r->positions[i] = 1;
 294         }
 295 }
 296
 297 /* The number of positions to advance the rotors at a time */
 298 static void
 299 RTR_advances(r)
 300         Rotorobj *r;
 301 {
 302         int i;
 303         for (i = 0; i < r->rotors; i++) {
 304                 r->advances[i] = 1;
 305         }
 306 }
 307
 308 /* Permute the E rotor, and make the D rotor its inverse
 309  * see Knuth for explanation of algorithm.
 310  */
 311 static void
 312 RTR_permute_rotor(r, e, d)
 313         Rotorobj *r;
 314         unsigned char *e;
 315         unsigned char *d;
 316 {
 317         short i = r->size;
 318         short q;
 319         unsigned char j;
 320         RTR_make_id_rotor(r,e);
 321         while (2 <= i) {
 322                 q = r_rand(r,i);
 323                 i--;
 324                 j = e[q];
 325                 e[q] = (unsigned char)e[i];
 326                 e[i] = (unsigned char)j;
 327                 d[j] = (unsigned char)i;
 328         }
 329         e[0] = (unsigned char)e[0];
 330         d[(e[0])] = (unsigned char)0;
 331 }
 332
 333 /* Given KEY (a list of 5 16 bit numbers), initialize the rotor machine.
 334  * Set the advancement, position, and permutation of the rotors
 335  */
 336 static void
 337 RTR_init(r)
 338         Rotorobj *r;
 339 {
 340         int i;
 341         set_seed(r);
 342         RTR_positions(r);
 343         RTR_advances(r);
 344         RTR_e_rotors(r);
 345         RTR_d_rotors(r);
 346         for (i = 0; i < r->rotors; i++) {
 347                 r->positions[i] = (unsigned char) r_rand(r,r->size);
 348                 r->advances[i] = (1+(2*(r_rand(r,r->size/2))));
 349                 RTR_permute_rotor(r,
 350                                   &(r->e_rotor[(i*r->size)]),
 351                                   &(r->d_rotor[(i*r->size)]));
 352         }
 353         r->isinited = TRUE;
 354 }
 355
 356 /* Change the RTR-positions vector, using the RTR-advances vector */
 357 static void
 358 RTR_advance(r)
 359         Rotorobj *r;
 360 {
 361         register int i=0, temp=0;
 362         if (r->size_mask) {
 363                 while (i < r->rotors) {
 364                         temp = r->positions[i] + r->advances[i];
 365                         r->positions[i] = temp & r->size_mask;
 366                         if ((temp >= r->size) && (i < (r->rotors - 1))) {
 367                                 r->positions[(i+1)] = 1 + r->positions[(i+1)];
 368                         }
 369                         i++;
 370                 }
 371         } else {
 372                 while (i < r->rotors) {
 373                         temp = r->positions[i] + r->advances[i];
 374                         r->positions[i] = temp%r->size;
 375                         if ((temp >= r->size) && (i < (r->rotors - 1))) {
 376                                 r->positions[(i+1)] = 1 + r->positions[(i+1)];
 377                         }
 378                         i++;
 379                 }
 380         }
 381 }
 382
 383 /* Encrypt the character P with the current rotor machine */
 384 static unsigned char
 385 RTR_e_char(r, p)
 386         Rotorobj *r;
 387         unsigned char p;
 388 {
 389         register int i=0;
 390         register unsigned char tp=p;
 391         if (r->size_mask) {
 392                 while (i < r->rotors) {
 393                         tp = r->e_rotor[(i*r->size) +
 394                                        (((r->positions[i] ^ tp) &
 395                                          r->size_mask))];
 396                         i++;
 397                 }
 398         } else {
 399                 while (i < r->rotors) {
 400                         tp = r->e_rotor[(i*r->size) +
 401                                        (((r->positions[i] ^ tp) %
 402                                          (unsigned int) r->size))];
 403                         i++;
 404                 }
 405         }
 406         RTR_advance(r);
 407         return ((unsigned char)tp);
 408 }
 409
 410 /* Decrypt the character C with the current rotor machine */
 411 static unsigned char
 412 RTR_d_char(r, c)
 413         Rotorobj *r;
 414         unsigned char c;
 415 {
 416         register int i = r->rotors - 1;
 417         register unsigned char tc = c;
 418
 419         if (r->size_mask) {
 420                 while (0 <= i) {
 421                         tc = (r->positions[i] ^
 422                               r->d_rotor[(i*r->size)+tc]) & r->size_mask;
 423                         i--;
 424                 }
 425         } else {
 426                 while (0 <= i) {
 427                         tc = (r->positions[i] ^
 428                               r->d_rotor[(i*r->size)+tc]) %
 429                                 (unsigned int) r->size;
 430                         i--;
 431                 }
 432         }
 433         RTR_advance(r);
 434         return(tc);
 435 }
 436
 437 /* Perform a rotor encryption of the region from BEG to END by KEY */
 438 static void
 439 RTR_e_region(r, beg, len, doinit)
 440         Rotorobj *r;
 441         unsigned char *beg;
 442         int len;
 443         int doinit;
 444 {
 445         register int i;
 446         if (doinit || r->isinited == FALSE)
 447                 RTR_init(r);
 448         for (i = 0; i < len; i++) {
 449                 beg[i] = RTR_e_char(r, beg[i]);
 450         }
 451 }
 452
 453 /* Perform a rotor decryption of the region from BEG to END by KEY */
 454 static void
 455 RTR_d_region(r, beg, len, doinit)
 456         Rotorobj *r;
 457         unsigned char *beg;
 458         int len;
 459         int doinit;
 460 {
 461         register int i;
 462         if (doinit || r->isinited == FALSE)
 463                 RTR_init(r);
 464         for (i = 0; i < len; i++) {
 465                 beg[i] = RTR_d_char(r, beg[i]);
 466         }
 467 }
 468
 469
 470 \f
 471 /* Rotor methods */
 472 static void
 473 rotor_dealloc(xp)
 474         Rotorobj *xp;
 475 {
 476         PyMem_XDEL(xp->e_rotor);
 477         PyMem_XDEL(xp->d_rotor);
 478         PyMem_XDEL(xp->positions);
 479         PyMem_XDEL(xp->advances);
 480         PyMem_DEL(xp);
 481 }
 482
 483 static PyObject *
 484 rotorobj_encrypt(self, args)
 485         Rotorobj *self;
 486         PyObject * args;
 487 {
 488         char *string = NULL;
 489         int len = 0;
 490         PyObject *rtn = NULL;
 491         char *tmp;
 492
 493         if (!PyArg_Parse(args, "s#", &string, &len))
 494                 return NULL;
 495         if (!(tmp = PyMem_NEW(char, len+5))) {
 496                 PyErr_NoMemory();
 497                 return NULL;
 498         }
 499         memset(tmp, '\0', len+1);
 500         memcpy(tmp, string, len);
 501         RTR_e_region(self, (unsigned char *)tmp, len, TRUE);
 502         rtn = PyString_FromStringAndSize(tmp, len);
 503         PyMem_DEL(tmp);
 504         return(rtn);
 505 }
 506
 507 static PyObject *
 508 rotorobj_encrypt_more(self, args)
 509         Rotorobj *self;
 510         PyObject * args;
 511 {
 512         char *string = NULL;
 513         int len = 0;
 514         PyObject *rtn = NULL;
 515         char *tmp;
 516
 517         if (!PyArg_Parse(args, "s#", &string, &len))
 518                 return NULL;
 519         if (!(tmp = PyMem_NEW(char, len+5))) {
 520                 PyErr_NoMemory();
 521                 return NULL;
 522         }
 523         memset(tmp, '\0', len+1);
 524         memcpy(tmp, string, len);
 525         RTR_e_region(self, (unsigned char *)tmp, len, FALSE);
 526         rtn = PyString_FromStringAndSize(tmp, len);
 527         PyMem_DEL(tmp);
 528         return(rtn);
 529 }
 530
 531 static PyObject *
 532 rotorobj_decrypt(self, args)
 533         Rotorobj *self;
 534         PyObject * args;
 535 {
 536         char *string = NULL;
 537         int len = 0;
 538         PyObject *rtn = NULL;
 539         char *tmp;
 540
 541         if (!PyArg_Parse(args, "s#", &string, &len))
 542                 return NULL;
 543         if (!(tmp = PyMem_NEW(char, len+5))) {
 544                 PyErr_NoMemory();
 545                 return NULL;
 546         }
 547         memset(tmp, '\0', len+1);
 548         memcpy(tmp, string, len);
 549         RTR_d_region(self, (unsigned char *)tmp, len, TRUE);
 550         rtn = PyString_FromStringAndSize(tmp, len);
 551         PyMem_DEL(tmp);
 552         return(rtn);
 553 }
 554
 555 static PyObject *
 556 rotorobj_decrypt_more(self, args)
 557         Rotorobj *self;
 558         PyObject * args;
 559 {
 560         char *string = NULL;
 561         int len = 0;
 562         PyObject *rtn = NULL;
 563         char *tmp;
 564
 565         if (!PyArg_Parse(args, "s#", &string, &len))
 566                 return NULL;
 567         if (!(tmp = PyMem_NEW(char, len+5))) {
 568                 PyErr_NoMemory();
 569                 return NULL;
 570         }
 571         memset(tmp, '\0', len+1);
 572         memcpy(tmp, string, len);
 573         RTR_d_region(self, (unsigned char *)tmp, len, FALSE);
 574         rtn = PyString_FromStringAndSize(tmp, len);
 575         PyMem_DEL(tmp);
 576         return(rtn);
 577 }
 578
 579 static PyObject *
 580 rotorobj_setkey(self, args)
 581         Rotorobj *self;
 582         PyObject * args;
 583 {
 584         char *key;
 585
 586         if (!PyArg_ParseTuple(args, "s", &key))
 587                 return NULL;
 588
 589         set_key(self, key);
 590         Py_INCREF(Py_None);
 591         return Py_None;
 592 }
 593
 594 static struct PyMethodDef
 595 rotorobj_methods[] = {
 596         {"encrypt",     (PyCFunction)rotorobj_encrypt},
 597         {"encryptmore", (PyCFunction)rotorobj_encrypt_more},
 598         {"decrypt",     (PyCFunction)rotorobj_decrypt},
 599         {"decryptmore", (PyCFunction)rotorobj_decrypt_more},
 600         {"setkey",      (PyCFunction)rotorobj_setkey, 1},
 601         {NULL,          NULL}           /* sentinel */
 602 };
 603
 604
 605 /* Return a rotor object's named attribute. */
 606 static PyObject *
 607 rotorobj_getattr(s, name)
 608         Rotorobj *s;
 609         char *name;
 610 {
 611         return Py_FindMethod(rotorobj_methods, (PyObject*)s, name);
 612 }
 613
 614
 615 statichere PyTypeObject Rotor_Type = {
 616         PyObject_HEAD_INIT(&PyType_Type)
 617         0,                              /*ob_size*/
 618         "rotor",                        /*tp_name*/
 619         sizeof(Rotorobj),               /*tp_size*/
 620         0,                              /*tp_itemsize*/
 621         /* methods */
 622         (destructor)rotor_dealloc,      /*tp_dealloc*/
 623         0,                              /*tp_print*/
 624         (getattrfunc)rotorobj_getattr,  /*tp_getattr*/
 625         0,                              /*tp_setattr*/
 626         0,                              /*tp_compare*/
 627         0,                              /*tp_repr*/
 628         0,                              /*tp_hash*/
 629 };
 630
 631
 632 static PyObject *
 633 rotor_rotor(self, args)
 634         PyObject * self;
 635         PyObject * args;
 636 {
 637         Rotorobj *r;
 638         char *string;
 639         int len;
 640         int num_rotors = 6;
 641
 642         if (!PyArg_ParseTuple(args, "s#|i", &string, &len, &num_rotors))
 643                 return NULL;
 644
 645         r = rotorobj_new(num_rotors, string);
 646         return (PyObject *)r;
 647 }
 648
 649
 650 \f
 651 static struct PyMethodDef
 652 rotor_methods[] = {
 653         {"newrotor",  rotor_rotor, 1},
 654         {NULL,        NULL}                  /* sentinel */
 655 };
 656
 657
 658 DL_EXPORT(void)
 659 initrotor()
 660 {
 661         (void)Py_InitModule("rotor", rotor_methods);
 662 }