RSA Encryption Backdoor

January 19, 2016

Since we programmed an RSA cryptosystem in a previous exercise, all we need now is a new key-generation function that provides a backdoor key. Here is the backdoor key a, which is determined in some way that we do not specify:

> (define a 11314087)

We first need a function that takes a p‘ or q‘ and returns the corresponding p or q; here we combine the algorithm given on the previous page with the RSA requirements of the previous exercise:

(define (backdoor x-prime e)
  (let loop ((k x-prime))
    (let ((x (+ (* a k) x-prime)))
      (if (or (< 1 (gcd e (- x 1)))
              (not (= (modulo x 4) 3))
              (not (prime? x)))
          (loop (+ k 1))
          x))))

Then we use that function to generate a key: keygen takes a key length (twice the length of the two semiprimes that comprise the key) and the encryption key e and returns n and d, so it has the same signature as the normal key-generation function:

(define (keygen t*2 e)
  (let* ((t (quotient t*2 2))
         (len (quotient t 4))
         (p-prime (random-prime len 2))
         (q-prime (random-prime len 2))
         (p (backdoor p-prime e))
         (q (backdoor q-prime e))
         (n (* p q))
         (d (inverse e (* (- p 1) (- q 1)))))
    (values n d)))

Notice that p‘ and q‘ are never exposed, nor is the backdoor key.

As an example, we’ll encipher the message “PRAXIS” as a base-26 number with A = 0, … Z = 25 and encrypt it using a 64-bit RSA cryptosystem, so t = 32 and both p‘ and q‘ have 8 bits:

> (define t*2 64)
> (define e 65537)
> (define n #f)
> (define d #f)
> (call-with-values
    (lambda () (keygen t*2 e))
    (lambda (nn dd)
      (set! n nn)
      (set! d dd))
> (display n)
4247324781037166041
> (display d)
646136198260976393

Now we can encrypt and decrypt our message:

> (crypt (encipher "PRAXIS") n e)
3852399687424634890
> (decipher (crypt 3852399687424634890 n d))
"PRAXIS"

As a demonstration of the value of the backdoor key, we first factor n; we’ll use Fermat’s method, which ought to be quick for two primes that are close to each other:

> (time (factors n))
(time (factors n))
    9415 collections
    471295 ms elapsed cpu time, including 482 ms collecting
    471521 ms elapsed real time, including 497 ms collecting
    39762298752 bytes allocated, including 39763382856 bytes reclaimed
(2375958427 1787625883)

About eight minutes; Fermat’s method isn’t all that fast. But since we know the backdoor key, we can factor n (mod a), which is very fast:

> (time (factors (modulo n a)))
(time (factors (modulo n ...)))
    no collections
    0 ms elapsed cpu time
    0 ms elapsed real time
    1192 bytes allocated
(157 137)

In zero time, we discover that p‘ and q‘ are 157 and 137. And now, to see the backdoor in action, we compute p and q, then compute n and d, and decrypt the message:

> (backdoor 157 e)
2375958427 ; p
> (backdoor 137 e)
1787625883 ; q
> (* 2375958427 1787625883)
4247324781037166041 ; n
> (inverse e (* 2375958426 1787625882))
646136198260976393 ; d
> (decipher (crypt 3852399687424634890
                   4247324781037166041
                   646136198260976393))
"PRAXIS"

Of course, an unwitting user can perform key generation, encryption and decryption without knowing that a backdoor key exists. There is no way of knowing that the encryption and decryption keys are “linked” to the secret backdoor key, and no way of recovering the backdoor key even if you know it exists (unless you know the exact algorithm used to compute a, which would probably be kept secret as a matter of law, although crypto experts would doubtless figure it out eventually).

You can run the program at http://ideone.com/tFdB4P, where you will also see all of the auxiliary code needed to make it work.

Advertisements

Pages: 1 2

One Response to “RSA Encryption Backdoor”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: