NTIC RSA and (Lack Of) Security

Section 11.6 RSA and (Lack Of) Security

We are now ready to discuss some elementary security issues regarding RSA. Remember, we aren't learning to be security experts here, and far more powerful techniques are available! But these are some underlying fundamentals.

🔗

Sage note 11.6.1. A final reminder to evaluate definitions.

If you're online, don't forget to evaluate the commands in the Sage cell below so we can use words as messages instead of just numbers.

xxxxxxxxxx
 
def encode(s): # Input must be in quotes!
    s = str(s).upper()
    return sum((ord(s[i])-64)*26^i for i in range(len(s)))
​
def decode(n):
    n = Integer(n)
    list = []
    while n != 0:
        if n%26==0:
            list.append(chr(64+26))
            n -= 1
        else:
            list.append(chr(n%26+64))
        n //=26
    return ''.join(list)

🔗

Subsection 11.6.1 Beating the man in the middle

🔗

First, remember one problem with Diffie-Hellman key exchange (Section 11.4). Someone who can control your messages can actually fake them. This can't happen with public-key systems (at least not as easily). Here's why.

🔗

Suppose I want to let someone verify I am who I say I am. In a public-key system, I never need to let

$f$ get known, so I encode my signature with

$f$ itself as the exponent!

🔗

First, I just turn my signature into a number. I'll just use the first three letters in order to keep the encoding small enough to use small primes.

xxxxxxxxxx
 
signature='Cri'
code=encode(signature)
print(code)

🔗

Then I raise it to the power of the secret key

$f\text{,}$ the inverse of the public key

$e\text{.}$

xxxxxxxxxx
 
p=89
q=97
n=p*q
phi=euler_phi(n)
e=71
f=mod(e,phi)^-1
secret=mod(code,n)^f
secret

🔗

Now anyone in the world can check my signature by raising this version of the signature to the public power

$e$ modulo

$n\text{.}$

xxxxxxxxxx
 
print(secret^e)
print(decode(secret^e))

🔗

The reason this works is because

$\begin{equation*} ef\equiv 1\text{ (mod }\phi(n)) \end{equation*}$

🔗

and

$ef=fe$ in a commutative setting:

$\begin{equation*} \left(Name^f\right)^e=\left(Name\right)^{ef}\equiv Name^1\equiv Name \text{ (mod }n) \end{equation*}$

🔗

Naturally, implementing this is somewhat more complex in real life (e.g. padding is used), but it is one major digital signing method implemented on many secure systems.

🔗

Interestingly, this concept also can be used in the opposite way²I am indebted to my colleague, Russ Tuck, for this observation.. Suppose that someone sends a message using their public signature as above – a message which later turns out to implicate him or her in illegal activity, a scandal, offensive behavior, etc. The author may wish to repudiate this message, but (at least in principle) the digital signature cannot be repudiated in the same way as other types of messages. (Of course, one can always say that one's private key was stolen, so it's not foolproof!)

🔗

Subsection 11.6.2 A cautionary tale

🔗

Lest you think we are now completely secure, let me warn you about one possible problem. Remember how we said above that it seems not to matter too much what

$e$ is? Well, that is sort of true, and sort of untrue.

🔗

Suppose we chose to send a message using the following primes and randomly (maybe) chosen exponent

$e\text{.}$ (Notice that if

$\gcd(e,\phi(pq))\neq 1\text{,}$ this code wouldn't have worked at all.)

xxxxxxxxxx
 
message='hiphop'
secret=encode(message)
p=197108347
q=591324977
e=52665067560570823
n=p*q
phi=(p-1)*(q-1)
code=mod(secret,n)^e
f=mod(e,phi)^-1
print("My encoded message is %s"%secret)
print("A big product of primes bigger than that is pq=(%s)(%s)=%s"%(p,q,n))
print("(which means my secret phi(n)=phi((%s)(%s))=(%s-1)(%s-1) is %s)"%(p,q,p,q,phi))
print("And I chose exponent %s"%e)
print("The encrypted message is %s^%s congruent to %s"%(secret,e,code))
print("The inverse of %s modulo %s is %s"%(e,phi,f))
print("And the decrypted message turns out to be:")
print(''.join(decode(code^f)))

🔗

The above cell just does the RSA algorithm for a particular case, verifying it works.

🔗

Now suppose Alice has sent Bob this message using Bob's impressive RSA key (above) of

$\begin{equation*} (n,e)=(116555088756283019,52665067560570823)\text{.} \end{equation*}$

🔗

Let me impersonate Eve, trying to snoop. On a hunch (or, as [C.2.3] puts it, after attending a seminar at a decryption conference), I figure I don't have much to lose by just trying random arithmetic, so I decide to just keep taking

$e$ th powers of the encrypted text (which was already raised to the

$e$ th power once).

xxxxxxxxxx
 
trial_decrypt=code
for i in [1..25]:
    trial_decrypt=trial_decrypt^e
    print(''.join(decode(trial_decrypt)))

🔗

What's this? You should see a meaningful message appear. Eve would barely have to do anything to decrypt this!

🔗

Subsection 11.6.3 The explanation

🔗

This circumstance may seem mysterious, but it really is related to mathematics we already used a number of times before. Remember that we could find an inverse for

$a$ modulo

$n$ by just taking powers of

$a\text{,}$ because

$\begin{equation*} a^{-1}\equiv a^{\phi(n)-1}\text{ (mod }n) \end{equation*}$

🔗

Similarly, for any possible message

$m$ and public key

$e\text{,}$ there will always be some power

$k$ of

$e$ such

$\begin{equation*} m^{e^k}\equiv m^1\text{ (mod }n) \end{equation*}$

🔗

which is the same as

$\begin{equation*} e^k\equiv 1\text{ (mod }\phi(n)) \end{equation*}$

🔗

For this to happen, we would have to coincidentally have that not only

$\gcd(e,n)=1$ (which we always pick), but also that

$\gcd(e,\phi(n))=1\text{.}$ Then Euler's Theorem 9.2.5 says that the order of

$e$ modulo

$\phi(n)$ is a divisor of

$\phi(n)\text{,}$ so we will sometimes find

$e$ where that order is a small divisor of

$\phi(n)\text{.}$

🔗

Of course, in real life this would only happen randomly, so you could just protect against it by checking the order of

$e$ modulo

$\phi(n)\text{.}$ Here's how I created this not-quite-random example!

xxxxxxxxxx
 
g = 7  # Pick something coprime to n
print(gcd(g,phi))
i = mod(g,phi) # look at it mod phi(n)
print(i.multiplicative_order())
print(factor(i.multiplicative_order()))

xxxxxxxxxx
 
j=i^( 11 * 13 * 37 * 1879 * 22973)  # take it to as high a power I can to reduce the order
print(j.multiplicative_order()) # make sure this is small
print(gcd(j,phi)) # check we still have the right gcd
print(j)

🔗

What was the problem here? The issue is that we had an

$n$ such that its group of units had elements of tiny order in its group of units. (Two levels deep here!)

🔗

More precisely, we had an

$n$ with a

$\phi(n)$ such that

$U_{\phi(n)}$ had elements of very small order in it, so that

$\begin{equation*} e^{very small order}\equiv 1\text{ (mod }\phi(n)) \end{equation*}$

🔗

was possible. How can we avoid this?

🔗

Subsection 11.6.4 A solution

🔗

When we found elements of big order (primitive roots, for prime modulus) in Chapter 10, we relied on having the original modulus

$p$ being prime. We did not tell the whole story, but we did do enough of what happens with other moduli to know that we should suspect that choosing

$n$ factoring as a small number of primes to powers should make it easy to find elements of big order in the group of units. (For instance, we saw that

$2^n$ had elements pretty close to being primitive roots.)

🔗

And we do know something about

$\phi(n)\text{.}$ Namely, since

$n=pq$ is the product of two primes, we know that

$\phi(n)=(p-1)(q-1)$ is also the product of two numbers. It would be too much to hope for those to be prime! After all,

$p-1$ and

$q-1$ will both be even, since

$p$ and

$q$ will be odd primes.

🔗

However, it's possible to pick

$p$ and

$q$ so that

$p-1=2p'$ and

$q-1=2q'\text{,}$ where

$p'$ and

$q'$ are both prime. In that case

$\begin{equation*} \phi(n)=\phi(pq)=\phi(p)\phi(q)=2p'2q'=4p'q' \end{equation*}$

🔗

so that

$\phi(n)$ at least is four times a product of (still big) prime numbers.

🔗

We will not prove it, but it turns out this is enough to guarantee the existence of elements of orders

$p'-1$ and

$q'-1$ in

$U_{\phi(pq)}\text{,}$ just like we had elements of order

$p-1$ in

$U_p\text{.}$ To be precise, we get elements of order

$\begin{equation*} p'-1 = \frac{p-1}{2}-1\text{ and }q'-1=\frac{q-1}{2}-1 \end{equation*}$

🔗

$\frac{p-1}{2}$ and

$\frac{q-1}{2}$ are both prime. Here is an example of this with very small

$p$ and

$q\text{,}$ where we at least have elements of order four.

xxxxxxxxxx
 
n = 7*11
phi = euler_phi(n)
[mod(i,phi).multiplicative_order() for i in [1..phi] if gcd(i,phi)==1]

🔗

Going backwards, we are looking for prime numbers

$p',q'$ such that

$2p'+1,2q'+1$ are also prime, and then we use

$p=2p'+1$ and

$q=2q'+1$ in RSA, finding an exponent that has big order in

$U_{\phi(n)}\text{.}$ In this example,

$p'=5$ and

$q'=3\text{.}$

🔗

Such primes

$p'$ and

$q'$ are called Germain primes, for French mathematician Sophie Germain – the only female number theorist of note before the twentieth century, and definitely an important figure. The primes

$p$ and

$q$ are then called safe primes, presumably because they might be ‘safe’ to use under some circumstances.

🔗

Research into security of number-theoretic cryptography is ongoing. There are practical points as well; as just one example, one ePrint discovered that 0.2% of a large set of public keys have “secret keys [which] are accessible to anyone who takes the trouble” to try to find them. Other studies have found even more – often because of poor randomness.

🔗

Another interesting vulnerability is that there is a significant (in practice, not in theory) chance that two RSA keys will share a (prime) factor. In another study it was found that not only did a nontrivial number of apparently unrelated keys share a factor (enabling their complete factorization), many keys were the same! These would still be hard to factor, but as the authors says, “[g]iven cryptographic key sizes, we would not expect to see devices generate a single duplicated key for the population sizes we examined if the keys were generated with sufficient entropy.” This chapter is just a small taste of issues to consider, and no substitute for having a real security professional!