Public Key Cryptography

CSC 105 - The Digital Age - Weinman



Summary:
This laboratory briefly applies some concepts of RSA-based public key cryptography.

Review

Recall that we choose two prime numbers, p and q and let
m
=
p×q
(1)
A
=
(p-1)×(q-1).
(2)
We then choose E < A such that E and A are relatively prime (share no common factors). The number E is the public key used to encrypt messages (which are really just bits, which can be interpreted as numbers). We then have to find a number D so that
(D×E)-1=k×A.
(3)
The numberD is the private key used to decrypt messages. The pair (E,m) are distributed publicly, while D is kept privately secret.
To encrypt a message t (for text), the sender calculates the cipher text using the formula
c=tE mod m.
(4)
To decrypt the cipher text the recipient calculates the original message text using the formula

t=cD mod m,
(5)
which requires the private key D.

Exercises

Preparation

To support the mathematical operations required, you may find it very helpful to launch the program gcalctool from a terminal. Launch this tool now.

A: Encryption

  1. Recall that the reading chose the following example values:
    m
    =
    10
    E
    =
    3
    D
    =
    7.
    Following the suggestion on page 3, decipher the message
    5
    7
    2
    9
    using equation 5 above and the alphabet code from the reading, repeated below
    A
    D
    E
    H
    N
    O
    R
    S
    T
    1
    2
    3
    4
    5
    6
    7
    8
    9
  2. The previous example was simple enough to work by hand (even though you probably didn't). Try the following example using
    m
    =
    115
    E
    =
    83
    D
    =
    35.
    Decipher the message
    43
    52.

B: Code Cracking

  1. The number 115 isn't that big and neither is m=133. There also aren't that many prime numbers less than 30. Recover the prime numbers p and q so that m=p×q=133.
  2. You can now calculate A=(p-1)×(q-1). Write out the prime factors of A. (Hint: Start with 2 and work your way up!)
    A=2×?
  3. Now the the encrypter had to choose E that shares no common factors (which you listed above) with A, but also a D such that
    (D×E)-1=k×A
    		(6)
    for some value of k.
    The take home: If you knew the public key E=35, how would you find D? The short answer is: the same way whoever generated the original key did. That problem must be easy!
If it is this "easy" to crack the code, why does the internet use RSA for most of its encryption? The answer is that real encryption uses prime numbers (which are "easy" to find) p and q that are much, much bigger; that is, they are longer bit strings.
It turns out that knowing m does not make it easy to recover p and q. We surmise this is one of those problems that requires time exponential in the size (number of bits) of m to solve. (However, the astute reader will note that we are not 100% sure ... )

Appendix: Why does RSA work?

Recall from equation (4) that the message text, interpreted as an integer, is encrypted by raising it to the power E using modular arithmetic. The message is subsequently decrypted by raising that value again to the power D. The cumulative encrypt-decrypt calculatio is thus

(tE mod m)D mod m.
(7)
While this equation looks somewhat daunting, we must now recognize the following important property of modular arithmetic (thank you number theorists!):
(q mod m)D mod m=qD mod m.
(8)
Using this relation in equation (7) above by letting q=tE, we have that
(tE mod m)D mod m=tED mod m.
So what help is that? This scheme only works if tED mod m gives us back the original text t. It turns out that indeed it does. We can prove it using some other convenient properties of modular arithmetic (thank you again number theorists!). When I get time, I may write them here. Until then, you can see more details at Wikipedia: http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Proofs_of_correctness (be careful that the author of our reading used symbols, perpetuated in this lab, that differ from the standards, which are utilized by the Wikipedians).