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 hardware 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       initialized 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
  60 #ifndef TRUE
  61 #define TRUE    1
  62 #endif
  63 #ifndef FALSE
  64 #define FALSE   0
  65 #endif
  66
  67 typedef struct {
  68         PyObject_HEAD
  69         int seed[3];
  70         short key[5];
  71         int  isinited;
  72         int  size;
  73         int  size_mask;
  74         int  rotors;
  75         unsigned char *e_rotor;              /* [num_rotors][size] */
  76         unsigned char *d_rotor;              /* [num_rotors][size] */
  77         unsigned char *positions;            /* [num_rotors] */
  78         unsigned char *advances;             /* [num_rotors] */
  79 } Rotorobj;
  80
  81 staticforward PyTypeObject Rotor_Type;
  82
  83 #define is_rotor(v)             ((v)->ob_type == &Rotor_Type)
  84
  85 \f
  86 /* This defines the necessary routines to manage rotor objects */
  87
  88 static void
  89 set_seed(Rotorobj *r)
  90 {
  91         r->seed[0] = r->key[0];
  92         r->seed[1] = r->key[1];
  93         r->seed[2] = r->key[2];
  94         r->isinited = FALSE;
  95 }
  96
  97 /* Return the next random number in the range [0.0 .. 1.0) */
  98 static double
  99 r_random(Rotorobj *r)
 100 {
 101         int x, y, z;
 102         double val, term;
 103
 104         x = r->seed[0];
 105         y = r->seed[1];
 106         z = r->seed[2];
 107
 108         x = 171 * (x % 177) - 2 * (x/177);
 109         y = 172 * (y % 176) - 35 * (y/176);
 110         z = 170 * (z % 178) - 63 * (z/178);
 111
 112         if (x < 0) x = x + 30269;
 113         if (y < 0) y = y + 30307;
 114         if (z < 0) z = z + 30323;
 115
 116         r->seed[0] = x;
 117         r->seed[1] = y;
 118         r->seed[2] = z;
 119
 120         term = (double)(
 121                 (((double)x)/(double)30269.0) +
 122                 (((double)y)/(double)30307.0) +
 123                 (((double)z)/(double)30323.0)
 124                 );
 125         val = term - (double)floor((double)term);
 126
 127         if (val >= 1.0)
 128                 val = 0.0;
 129
 130         return val;
 131 }
 132
 133 static short
 134 r_rand(Rotorobj *r, short s)
 135 {
 136         return (short)((short)(r_random(r) * (double)s) % s);
 137 }
 138
 139 static void
 140 set_key(Rotorobj *r, char *key)
 141 {
 142         unsigned long k1=995, k2=576, k3=767, k4=671, k5=463;
 143         size_t i;
 144         size_t len = strlen(key);
 145
 146         for (i = 0; i < len; i++) {
 147                 unsigned short ki = Py_CHARMASK(key[i]);
 148
 149                 k1 = (((k1<<3 | k1>>13) + ki) & 65535);
 150                 k2 = (((k2<<3 | k2>>13) ^ ki) & 65535);
 151                 k3 = (((k3<<3 | k3>>13) - ki) & 65535);
 152                 k4 = ((ki - (k4<<3 | k4>>13)) & 65535);
 153                 k5 = (((k5<<3 | k5>>13) ^ ~ki) & 65535);
 154         }
 155         r->key[0] = (short)k1;
 156         r->key[1] = (short)(k2|1);
 157         r->key[2] = (short)k3;
 158         r->key[3] = (short)k4;
 159         r->key[4] = (short)k5;
 160
 161         set_seed(r);
 162 }
 163
 164
 165 \f
 166 /* These define the interface to a rotor object */
 167 static Rotorobj *
 168 rotorobj_new(int num_rotors, char *key)
 169 {
 170         Rotorobj *xp;
 171
 172         xp = PyObject_New(Rotorobj, &Rotor_Type);
 173         if (xp == NULL)
 174                 return NULL;
 175         set_key(xp, key);
 176
 177         xp->size = 256;
 178         xp->size_mask = xp->size - 1;
 179         xp->size_mask = 0;
 180         xp->rotors = num_rotors;
 181         xp->e_rotor = NULL;
 182         xp->d_rotor = NULL;
 183         xp->positions = NULL;
 184         xp->advances = NULL;
 185
 186         if (!(xp->e_rotor = PyMem_NEW(unsigned char, num_rotors * xp->size)))
 187                 goto finally;
 188         if (!(xp->d_rotor = PyMem_NEW(unsigned char, num_rotors * xp->size)))
 189                 goto finally;
 190         if (!(xp->positions = PyMem_NEW(unsigned char, num_rotors)))
 191                 goto finally;
 192         if (!(xp->advances = PyMem_NEW(unsigned char, num_rotors)))
 193                 goto finally;
 194
 195         return xp;
 196
 197   finally:
 198         if (xp->e_rotor)
 199                 PyMem_DEL(xp->e_rotor);
 200         if (xp->d_rotor)
 201                 PyMem_DEL(xp->d_rotor);
 202         if (xp->positions)
 203                 PyMem_DEL(xp->positions);
 204         if (xp->advances)
 205                 PyMem_DEL(xp->advances);
 206         Py_DECREF(xp);
 207         return (Rotorobj*)PyErr_NoMemory();
 208 }
 209
 210 \f
 211 /* These routines implement the rotor itself */
 212
 213 /*  Here is a fairly sophisticated {en,de}cryption system.  It is based on
 214     the idea of a "rotor" machine.  A bunch of rotors, each with a
 215     different permutation of the alphabet, rotate around a different amount
 216     after encrypting one character.  The current state of the rotors is
 217     used to encrypt one character.
 218
 219     The code is smart enough to tell if your alphabet has a number of
 220     characters equal to a power of two.  If it does, it uses logical
 221     operations, if not it uses div and mod (both require a division).
 222
 223     You will need to make two changes to the code 1) convert to c, and
 224     customize for an alphabet of 255 chars 2) add a filter at the begining,
 225     and end, which subtracts one on the way in, and adds one on the way
 226     out.
 227
 228     You might wish to do some timing studies.  Another viable alternative
 229     is to "byte stuff" the encrypted data of a normal (perhaps this one)
 230     encryption routine.
 231
 232     j'
 233
 234  */
 235
 236 /* Note: the C code here is a fairly straightforward transliteration of a
 237  * rotor implemented in lisp.  The original lisp code has been removed from
 238  * this file to for simplification, but I've kept the docstrings as
 239  * comments in front of the functions.
 240  */
 241
 242
 243 /* Set ROTOR to the identity permutation */
 244 static void
 245 RTR_make_id_rotor(Rotorobj *r, unsigned char *rtr)
 246 {
 247         register int j;
 248         register int size = r->size;
 249         for (j = 0; j < size; j++) {
 250                 rtr[j] = (unsigned char)j;
 251         }
 252 }
 253
 254
 255 /* The current set of encryption rotors */
 256 static void
 257 RTR_e_rotors(Rotorobj *r)
 258 {
 259         int i;
 260         for (i = 0; i < r->rotors; i++) {
 261                 RTR_make_id_rotor(r, &(r->e_rotor[(i*r->size)]));
 262         }
 263 }
 264
 265 /* The current set of decryption rotors */
 266 static void
 267 RTR_d_rotors(Rotorobj *r)
 268 {
 269         register int i, j;
 270         for (i = 0; i < r->rotors; i++) {
 271                 for (j = 0; j < r->size; j++) {
 272                         r->d_rotor[((i*r->size)+j)] = (unsigned char)j;
 273                 }
 274         }
 275 }
 276
 277 /* The positions of the rotors at this time */
 278 static void
 279 RTR_positions(Rotorobj *r)
 280 {
 281         int i;
 282         for (i = 0; i < r->rotors; i++) {
 283                 r->positions[i] = 1;
 284         }
 285 }
 286
 287 /* The number of positions to advance the rotors at a time */
 288 static void
 289 RTR_advances(Rotorobj *r)
 290 {
 291         int i;
 292         for (i = 0; i < r->rotors; i++) {
 293                 r->advances[i] = 1;
 294         }
 295 }
 296
 297 /* Permute the E rotor, and make the D rotor its inverse
 298  * see Knuth for explanation of algorithm.
 299  */
 300 static void
 301 RTR_permute_rotor(Rotorobj *r, unsigned char *e, unsigned char *d)
 302 {
 303         short i = r->size;
 304         short q;
 305         unsigned char j;
 306         RTR_make_id_rotor(r,e);
 307         while (2 <= i) {
 308                 q = r_rand(r,i);
 309                 i--;
 310                 j = e[q];
 311                 e[q] = (unsigned char)e[i];
 312                 e[i] = (unsigned char)j;
 313                 d[j] = (unsigned char)i;
 314         }
 315         e[0] = (unsigned char)e[0];
 316         d[(e[0])] = (unsigned char)0;
 317 }
 318
 319 /* Given KEY (a list of 5 16 bit numbers), initialize the rotor machine.
 320  * Set the advancement, position, and permutation of the rotors
 321  */
 322 static void
 323 RTR_init(Rotorobj *r)
 324 {
 325         int i;
 326         set_seed(r);
 327         RTR_positions(r);
 328         RTR_advances(r);
 329         RTR_e_rotors(r);
 330         RTR_d_rotors(r);
 331         for (i = 0; i < r->rotors; i++) {
 332                 r->positions[i] = (unsigned char) r_rand(r, (short)r->size);
 333                 r->advances[i] = (1+(2*(r_rand(r, (short)(r->size/2)))));
 334                 RTR_permute_rotor(r,
 335                                   &(r->e_rotor[(i*r->size)]),
 336                                   &(r->d_rotor[(i*r->size)]));
 337         }
 338         r->isinited = TRUE;
 339 }
 340
 341 /* Change the RTR-positions vector, using the RTR-advances vector */
 342 static void
 343 RTR_advance(Rotorobj *r)
 344 {
 345         register int i=0, temp=0;
 346         if (r->size_mask) {
 347                 while (i < r->rotors) {
 348                         temp = r->positions[i] + r->advances[i];
 349                         r->positions[i] = temp & r->size_mask;
 350                         if ((temp >= r->size) && (i < (r->rotors - 1))) {
 351                                 r->positions[(i+1)] = 1 + r->positions[(i+1)];
 352                         }
 353                         i++;
 354                 }
 355         } else {
 356                 while (i < r->rotors) {
 357                         temp = r->positions[i] + r->advances[i];
 358                         r->positions[i] = temp%r->size;
 359                         if ((temp >= r->size) && (i < (r->rotors - 1))) {
 360                                 r->positions[(i+1)] = 1 + r->positions[(i+1)];
 361                         }
 362                         i++;
 363                 }
 364         }
 365 }
 366
 367 /* Encrypt the character P with the current rotor machine */
 368 static unsigned char
 369 RTR_e_char(Rotorobj *r, unsigned char p)
 370 {
 371         register int i=0;
 372         register unsigned char tp=p;
 373         if (r->size_mask) {
 374                 while (i < r->rotors) {
 375                         tp = r->e_rotor[(i*r->size) +
 376                                        (((r->positions[i] ^ tp) &
 377                                          r->size_mask))];
 378                         i++;
 379                 }
 380         } else {
 381                 while (i < r->rotors) {
 382                         tp = r->e_rotor[(i*r->size) +
 383                                        (((r->positions[i] ^ tp) %
 384                                          (unsigned int) r->size))];
 385                         i++;
 386                 }
 387         }
 388         RTR_advance(r);
 389         return ((unsigned char)tp);
 390 }
 391
 392 /* Decrypt the character C with the current rotor machine */
 393 static unsigned char
 394 RTR_d_char(Rotorobj *r, unsigned char c)
 395 {
 396         register int i = r->rotors - 1;
 397         register unsigned char tc = c;
 398
 399         if (r->size_mask) {
 400                 while (0 <= i) {
 401                         tc = (r->positions[i] ^
 402                               r->d_rotor[(i*r->size)+tc]) & r->size_mask;
 403                         i--;
 404                 }
 405         } else {
 406                 while (0 <= i) {
 407                         tc = (r->positions[i] ^
 408                               r->d_rotor[(i*r->size)+tc]) %
 409                                 (unsigned int) r->size;
 410                         i--;
 411                 }
 412         }
 413         RTR_advance(r);
 414         return(tc);
 415 }
 416
 417 /* Perform a rotor encryption of the region from BEG to END by KEY */
 418 static void
 419 RTR_e_region(Rotorobj *r, unsigned char *beg, int len, int doinit)
 420 {
 421         register int i;
 422         if (doinit || r->isinited == FALSE)
 423                 RTR_init(r);
 424         for (i = 0; i < len; i++) {
 425                 beg[i] = RTR_e_char(r, beg[i]);
 426         }
 427 }
 428
 429 /* Perform a rotor decryption of the region from BEG to END by KEY */
 430 static void
 431 RTR_d_region(Rotorobj *r, unsigned char *beg, int len, int doinit)
 432 {
 433         register int i;
 434         if (doinit || r->isinited == FALSE)
 435                 RTR_init(r);
 436         for (i = 0; i < len; i++) {
 437                 beg[i] = RTR_d_char(r, beg[i]);
 438         }
 439 }
 440
 441
 442 \f
 443 /* Rotor methods */
 444 static void
 445 rotor_dealloc(Rotorobj *xp)
 446 {
 447         if (xp->e_rotor)
 448                 PyMem_DEL(xp->e_rotor);
 449         if (xp->d_rotor)
 450                 PyMem_DEL(xp->d_rotor);
 451         if (xp->positions)
 452                 PyMem_DEL(xp->positions);
 453         if (xp->advances)
 454                 PyMem_DEL(xp->advances);
 455         PyObject_Del(xp);
 456 }
 457
 458 static PyObject *
 459 rotorobj_encrypt(Rotorobj *self, PyObject *args)
 460 {
 461         char *string = NULL;
 462         int len = 0;
 463         PyObject *rtn = NULL;
 464         char *tmp;
 465
 466         if (!PyArg_Parse(args, "s#", &string, &len))
 467                 return NULL;
 468         if (!(tmp = PyMem_NEW(char, len+5))) {
 469                 PyErr_NoMemory();
 470                 return NULL;
 471         }
 472         memset(tmp, '\0', len+1);
 473         memcpy(tmp, string, len);
 474         RTR_e_region(self, (unsigned char *)tmp, len, TRUE);
 475         rtn = PyString_FromStringAndSize(tmp, len);
 476         PyMem_DEL(tmp);
 477         return(rtn);
 478 }
 479
 480 static PyObject *
 481 rotorobj_encrypt_more(Rotorobj *self, PyObject *args)
 482 {
 483         char *string = NULL;
 484         int len = 0;
 485         PyObject *rtn = NULL;
 486         char *tmp;
 487
 488         if (!PyArg_Parse(args, "s#", &string, &len))
 489                 return NULL;
 490         if (!(tmp = PyMem_NEW(char, len+5))) {
 491                 PyErr_NoMemory();
 492                 return NULL;
 493         }
 494         memset(tmp, '\0', len+1);
 495         memcpy(tmp, string, len);
 496         RTR_e_region(self, (unsigned char *)tmp, len, FALSE);
 497         rtn = PyString_FromStringAndSize(tmp, len);
 498         PyMem_DEL(tmp);
 499         return(rtn);
 500 }
 501
 502 static PyObject *
 503 rotorobj_decrypt(Rotorobj *self, PyObject *args)
 504 {
 505         char *string = NULL;
 506         int len = 0;
 507         PyObject *rtn = NULL;
 508         char *tmp;
 509
 510         if (!PyArg_Parse(args, "s#", &string, &len))
 511                 return NULL;
 512         if (!(tmp = PyMem_NEW(char, len+5))) {
 513                 PyErr_NoMemory();
 514                 return NULL;
 515         }
 516         memset(tmp, '\0', len+1);
 517         memcpy(tmp, string, len);
 518         RTR_d_region(self, (unsigned char *)tmp, len, TRUE);
 519         rtn = PyString_FromStringAndSize(tmp, len);
 520         PyMem_DEL(tmp);
 521         return(rtn);
 522 }
 523
 524 static PyObject *
 525 rotorobj_decrypt_more(Rotorobj *self, PyObject *args)
 526 {
 527         char *string = NULL;
 528         int len = 0;
 529         PyObject *rtn = NULL;
 530         char *tmp;
 531
 532         if (!PyArg_Parse(args, "s#", &string, &len))
 533                 return NULL;
 534         if (!(tmp = PyMem_NEW(char, len+5))) {
 535                 PyErr_NoMemory();
 536                 return NULL;
 537         }
 538         memset(tmp, '\0', len+1);
 539         memcpy(tmp, string, len);
 540         RTR_d_region(self, (unsigned char *)tmp, len, FALSE);
 541         rtn = PyString_FromStringAndSize(tmp, len);
 542         PyMem_DEL(tmp);
 543         return(rtn);
 544 }
 545
 546 static PyObject *
 547 rotorobj_setkey(Rotorobj *self, PyObject *args)
 548 {
 549         char *key;
 550
 551         if (!PyArg_ParseTuple(args, "s:setkey", &key))
 552                 return NULL;
 553
 554         set_key(self, key);
 555         Py_INCREF(Py_None);
 556         return Py_None;
 557 }
 558
 559 static struct PyMethodDef
 560 rotorobj_methods[] = {
 561         {"encrypt",     (PyCFunction)rotorobj_encrypt},
 562         {"encryptmore", (PyCFunction)rotorobj_encrypt_more},
 563         {"decrypt",     (PyCFunction)rotorobj_decrypt},
 564         {"decryptmore", (PyCFunction)rotorobj_decrypt_more},
 565         {"setkey",      (PyCFunction)rotorobj_setkey, 1},
 566         {NULL,          NULL}           /* sentinel */
 567 };
 568
 569
 570 /* Return a rotor object's named attribute. */
 571 static PyObject *
 572 rotorobj_getattr(Rotorobj *s, char *name)
 573 {
 574         return Py_FindMethod(rotorobj_methods, (PyObject*)s, name);
 575 }
 576
 577
 578 statichere PyTypeObject Rotor_Type = {
 579         PyObject_HEAD_INIT(NULL)
 580         0,                              /*ob_size*/
 581         "rotor",                        /*tp_name*/
 582         sizeof(Rotorobj),               /*tp_size*/
 583         0,                              /*tp_itemsize*/
 584         /* methods */
 585         (destructor)rotor_dealloc,      /*tp_dealloc*/
 586         0,                              /*tp_print*/
 587         (getattrfunc)rotorobj_getattr,  /*tp_getattr*/
 588         0,                              /*tp_setattr*/
 589         0,                              /*tp_compare*/
 590         0,                              /*tp_repr*/
 591         0,                              /*tp_hash*/
 592 };
 593
 594
 595 static PyObject *
 596 rotor_rotor(PyObject *self, PyObject *args)
 597 {
 598         Rotorobj *r;
 599         char *string;
 600         int len;
 601         int num_rotors = 6;
 602
 603         if (!PyArg_ParseTuple(args, "s#|i:newrotor", &string, &len, &num_rotors))
 604                 return NULL;
 605
 606         r = rotorobj_new(num_rotors, string);
 607         return (PyObject *)r;
 608 }
 609
 610
 611 \f
 612 static struct PyMethodDef
 613 rotor_methods[] = {
 614         {"newrotor",  rotor_rotor, 1},
 615         {NULL,        NULL}                  /* sentinel */
 616 };
 617
 618
 619 DL_EXPORT(void)
 620 initrotor(void)
 621 {
 622         Rotor_Type.ob_type = &PyType_Type;
 623         (void)Py_InitModule("rotor", rotor_methods);
 624 }