## 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 11_{2}. 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.

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.