RSA Security – Some random notes

Posted on by paschmann

RSA

A good simple overview: https://simple.wikipedia.org/wiki/RSA_algorithm
https://www.npmjs.com/package/big-integer
https://www.youtube.com/watch?v=vgTtHV04xRI

6 Year old RSA explanation: If you look at a cake, its not that easy to figure out what or how much ingredients went in to making it. But if you have some milk, flour, sugar you can mix those things together to make a cake.

10 Year old: Its easy to multiple numbers together, but its not easy to figure out what are the biggest numbers you can multiply together to make that number.

Nice analogy: Its like looking for a phone number in a phone book – if you know the number its hard to find their first and last name. But if you know their name, its really easy to find their telephone number.

FYI:

  • RSA naming scheme changed from bits to digits. Now RSA-300 = 300 digits. Then RSA-2048 = 617 digits = RSA-617

Hacking RSA –
https://github.com/radii/msieve

Hacking RSA uses the numeric public exponent from the public key and tries to calculate its largest common multiple factors (p and q) – from those two numbers you can calculate the private Exponent (Private key)

  • This can be done using a General Number Field Sieve (Good at factoring integers > 10^100

Quantum Notes:

-----BEGIN RSA PRIVATE KEY-----
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
-----END RSA PRIVATE KEY--

-----BEGIN RSA PUBLIC KEY-----
RSAPublicKey ::= SEQUENCE {
modulus INTEGER, -- n
publicExponent INTEGER -- e
}
-----END RSA PUBLIC KEY-----
  • Basics:
    • Has 2 algorithms
      • Key generation
        • Complex part
        • Generates both public and private key
        • To generate keys
          • Generate large (1024+) prime numbers (p, q). We use a large random number generator, then check if it is a prime. We use Rabin-miller primality tester to test this (which is super fast and is a probablistic! test. 1/(2^128)
          • Modulus – Calculate modulus n by multiplying p x q. But, given just n, there is no known algorithm to efficiently determining n’s prime factors. In fact, it is considered a hard problem. I am going to bold this next statement for effect: The foundation of RSA’s security relies upon the fact that given a composite number, it is considered a hard problem to determine it’s prime factors.
          • Totient of n needs to be generated. ϕ(n)=(p−1)⋅(q−1). If we know the primes, its easy to calculate the totient.
          • public key, a prime number is calculated from the range [3, ϕ(n)] that has the greatest common divisor of 1 with ϕ(n) expressed as e. Actually its a key pair (e, n)
          • private key, because the prime in above step is the gcd (greatest common divisor of 1 with ϕ(n). We are able to determine its inverse with respect to mod ϕ(n). the multiplicative inverse of the public key with respect to ϕ(n)ϕ(n) can be efficiently and quickly determined using the Extended Euclidean Algorithm. This multiplicative inverse is the private key. The common notation for expressing the private key is dd. So in effect, we have the following equation (one of the most important equations in RSA):
          • e * d = 1 mod ϕ(n)
          • Just like the public key, the private key is also a key pair of the exponent d and modulus n:
          • (d,n)
      • RSA function evaluation
        • takes point x and key k and produces either an encrypted result or plain text.
  1. Select primes p=11, q=3.
  2. n = pq = 11.3 = 33
    phi = (p-1)(q-1) = 10.2 = 20
  3. Choose e=3
    Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
    and check gcd(e, q-1) = gcd(3, 2) = 1
    therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1
  4. Compute d such that ed ≡ 1 (mod phi)
    i.e. compute d = (1/e) mod phi = (1/3) mod 20
    i.e. find a value for d such that phi divides (ed-1)
    i.e. find d such that 20 divides 3d-1.
    Simple testing (d = 1, 2, …) gives d = 7
    Check: ed-1 = 3.7 – 1 = 20, which is divisible by phi.
  5. Public key = (n, e) = (33, 3)
    Private key = (n, d) = (33, 7).
    This is actually the smallest possible value for the modulus n for which the RSA algorithm works.
    Now say we want to encrypt the message m = 7,
    c=memodn=73mod33=343mod33=13c=memodn=73mod33=343mod33=13.
    Hence the ciphertext c = 13.
    To check decryption we compute
    m′=cdmodn=137mod33=7m′=cdmodn=137mod33=7.
    Note that we don’t have to calculate the full value of 13 to the power 7 here. We can make use of the fact that
    a=bcmodn=(bmodn)⋅(cmodn)modna=bcmodn=(bmodn)⋅(cmodn)modn
    so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the final value.
    One way of calculating m’ is as follows:-
    Note that any number can be expressed as a sum of powers of 2. In particular 7 = 4 + 2 + 1.
    So first compute values of 132,134,138,…132,134,138,… by repeatedly squaring successive values modulo 33.
    132=169≡4,134=4.4=16,138=16.16=256≡25132=169≡4,134=4.4=16,138=16.16=256≡25.
    Then, since 7 = 4 + 2 + 1, we have m′=137=13(4+2+1)=134.132.131m′=137=13(4+2+1)=134.132.131
    ≡16×4×13=832≡7(mod33)≡16×4×13=832≡7(mod33)

Now if we calculate the ciphertext c for all the possible values of m (0 to 32), we get

m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
c 0 1 8 27 31 26 18 13 17 3 10 11 12 19 5 9 4

m 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
c 29 24 28 14 21 22 23 30 16 20 15 7 2 6 25 32

Note that all 33 values of m (0 to 32) map to a unique code c in the same range in a sort of random manner. In this case we have nine values of m that map to the same value of c – these are known as unconcealed messages. m = 0, 1 and n-1 will always do this for any nn, no matter how large. But in practice, these shouldn’t be a problem when we use large values for nn in the order of several hundred bits.

If we wanted to use this system to keep secrets, we could let A=2, B=3, …, Z=27. (We specifically avoid 0 and 1 here for the reason given above). Thus the plaintext message “HELLOWORLD” would be represented by the set of integers m1,m2,…m1,m2,…

(9,6,13,13,16,24,16,19,13,5)

Using our table above, we obtain ciphertext integers c1,c2,…c1,c2,…
(3,18,19,19,4,30,4,28,19,26)

Note that this example is no more secure than using a simple Caesar substitution cipher, but it serves to illustrate a simple example of the mechanics of RSA encryption.

Remember that calculating memodnmemodn is easy, but calculating the inverse c−emodnc−emodn is very difficult, well, for large n’s anyway. However, if we can factor n into its prime factors p and q, the solution becomes easy again, even for large n’s. Obviously, if we can get hold of the secret exponent d, the solution is easy, too.