## Rabin’s Cryptosystem

### November 22, 2011

We begin with the key generator, which is similar to the one for the exercise on RSA cryptography; input is the number of bits k, output is the set of five values n, p, q, a, b, and the process simply picks a random v in the appropriate range and keeps incrementing it by 1 until a suitable v is found:

```(define (keygen k)   (define (gen k)     (let loop ((v (randint (expt 2 (- k 1)) (expt 2 k))))       (if (and (prime? v) (= (modulo v 4) 3)) v         (loop (+ v 1)))))   (let* ((k2 (quotient k 2)) (p (gen k2)) (q (gen k2)) (n (* p q)))     (call-with-values       (lambda () (euclid p q))       (lambda (a b g) (values n p q a b)))))```

Then encryption and decryption follow the formulas:

```(define (encrypt m n)   (let ((m (+ (* m 256) 255)))     (expm m 2 n)))```

```(define (decrypt c n p q a b)   (let* ((r (expm c (/ (+ p 1) 4) p))          (s (expm c (/ (+ q 1) 4) q))          (aps (* a p s)) (bqr (* b q r))          (x (modulo (+ aps bqr) n))          (y (modulo (- aps bqr) n))          (m1 x) (m2 (modulo (- x) n))          (m3 y) (m4 (modulo (- y) n)))     (cond ((= (remainder m1 256) 255) (quotient m1 256))           ((= (remainder m2 256) 255) (quotient m2 256))           ((= (remainder m3 256) 255) (quotient m3 256))           ((= (remainder m4 256) 255) (quotient m4 256))           (else (error 'decrypt "oops")))))```

To make a system for passing full messages, we assume 8-bit ascii and choose a block size of 32 bits consisting of 24 bits of payload and 8 bits of padding; the 24 payload bits consist of 3 bytes of the message, and the 8 padding bits will all be 1-bits. The key length will also be 32 bits. We’ll mark the end of the message as recommended by Bruce Schneier by adding k blocks of the byte k, where k is the number of bytes needed to fill out the final block; if the message completely fills the last block, we add another block with 3 blocks of 112. Thus, the 18-character message “Programming Praxis” will be split into 6 blocks, with a full trailing block added to mark the end of the message. For real security, of course, you would want a somewhat larger block size and key length.

Two functions `prepare` and `unprepare` split the message into blocks, add the trailing block, and delete it at the end:

```(define (prepare str n)   (let ((len (- n (modulo (string-length str) n))))     (string->list       (string-append str         (make-string len (integer->char len))))))```

```(define (unprepare xs)   (let loop ((xs (reverse xs)))     (if (char=? (car xs) (cadr xs))         (loop (cdr xs))         (reverse (cdr xs)))))```

Two functions `chars->num` and `num->chars` convert back and forth between character blocks and integers:

```(define (chars->num cs)   (let loop ((cs cs) (n 0))     (if (null? cs) n       (loop (cdr cs)         (+ (* n 256) (char->integer (car cs)))))))```

```(define (num->chars n)   (let loop ((n n) (cs (list)))     (if (zero? n) cs       (loop (quotient n 256)         (cons (integer->char (remainder n 256)) cs)))))```

With those auxiliary functions available, we are ready to encipher and decipher the message. The two functions `encipher` and `decipher` are duals of each other, calling opposite functions in reverse order:

```(define (encipher plaintext key blocksize)   (list->string     (apply append       (map num->chars         (map (lambda (m) (encrypt m key))           (map chars->num             (splits blocksize               (prepare plaintext blocksize))))))))```

```(define (decipher ciphertext n p q a b blocksize)   (list->string     (unprepare       (apply append         (map num->chars           (map (lambda (c) (decrypt c n p q a b))             (map chars->num               (splits (+ blocksize 1)                 (string->list ciphertext)))))))))```

Here’s an example:

```> (keygen 32) 2090723993 61027 34259 -14246 25377 > (decipher     (encipher "Programming Praxis" 2090723993 3)     2090723993 61027 34259 -14246 25377 3) "Programming Praxis"```

We used split, randint and expm from the Standard Prelude, `euclid` and `prime?` from previous exercises, and wrote a helper function `splits` not shown above. You can run the program at http://programmingpraxis.codepad.org/wyHgxfpg.

Pages: 1 2

### One Response to “Rabin’s Cryptosystem”

1. khatija sarwat said

I am doing a project on this technique, i have very well understood the algorithm and the calculations involved in encrypting and decrypting the message text. know i want to implement this algorithm using verilog language for both encryption and decryption, can you please provide the guidance sir, like how to start up.