Tuesday, May 22, 2012

Factoring big numbers and RSA

Last week I came across this article. It's an interesting report indeed and with this post I will explain what is the implication. But first of all, let's quickly recall what RSA encryption is.

There is a message m which needs to be encrypted. There is a public key (e, n) and a private key (d, n). Message is encrypted in the following way c = me (mod n). Cipher text is decrypted in the following way m = cd (mod n). Puting all these together me⋅d ≡ m (mod n) and if m and n are co-prime then me⋅d-1 ≡ 1 (mod n). n is selected to be a product of two distinct prime numbers n = p⋅q and, according to the Euler's theorem, mφ(n) ≡ 1 mod n. Now e and d (exponents of the public/private keys) are selected so that e⋅d - 1 ≡ 0 (mod φ(n)) or e⋅d - 1 = k⋅φ(n), k - integer.

Because n is a product of really big prime numbers (thus n is a big number itself), then factoring it is a really complicated problem, considering "limited" computational power of the modern computers and the fact that factoring is an exponential (in terms of complexity) problem. As a result, computing φ(n), which in this particular case is φ(n) = (p - 1)⋅(q - 1), is also a complicated problem.

However, computing the greatest common divisor (GCD) isn't a complicated problem. As a result, if two public keys (e1, n1) and (e2, n2) are spotted, so that GCD(n1, n2) > 1, then decoding the relevant messages m1 and m2 becomes and easy task and this is the topic of the article I have mentioned at the top of this post.

Now, let's do a quick test. Imagine the following two public keys and associated cipher texts:

e1 = 65537
n1 = 59271838373237712241010698426785545947980750376894660532845611609385295
     49357464245996603984250810283460055082118943354872215289998388427726673
     74160929852573051680099378617005092405110706474184136037559125038434888
     56979904991517729100725512850421664634705274281314737938901139871448406
     073842088742598680079967
cipher1 = "J\u00c1R\u0090\u00e1\u00f4\u008b5My\u00f8\u00a1\u00f4>\u00a2\u00c3\u0010
           \u00bd\u00eb\u00cc&\u007fb\u001aC$\u001d\u00c5\u00b7\u00cdz\u00b7\u0017
           \u008a#9\u0012\u0089\u00feao\u0019\u009c\u00eb\u00b0>\u0086\u009b
           \u001d3~b0-u\u00fc\u0004!\rc\\\u00cb$\u0091\u009e\u00a1N\u009d2\u00ff
           \u0019\u009a9vH.\u00d5\u00e7m\u00a9m\u00ea^\u00d3T$\u00d7\u00d7\u0011
           \u0081\u00e4B\u009b~\u008c$\u00a6K\u008a\u00dc`\u00b4\u009cu\u00fb\u00c2
           \u0006\u00d1\u00bb\u00b9\u00a0\u008f\u00d2\u00bc\u0002\u00f6#\u001f\u001dM
           \u00bb\u0098\u00f2\u00a0\u009fO\u0080"

e2 = 65537
n2 = 72216220929585874029800250341144628594049328751082632793975238142970345
     80195859400832155769761460789049220801438471143407662437503457520665980
     33488377571129629910281750410842883648532072455460838627134172456428247
     65387577331828704441227356582723560291425753389466410790421096831823015
     438162111864463275922441
cipher2 = ".\u00fd9\u008dc\u00da\u00f9o\u00f5Vl\u00fb\u0087\u00ed\u00d5 \u00ee\u00cf
           \u0097~\u00d8T\u00f9.\u0018\u00b1\u00d5n^\u00a0\rA\u00e0\u001d\u00d5
           \u00c8:D\u00c9\u0014o\u00de\u00dbo\u00f9>)bc'a\u00a2\u008e\u00c1|\u00dd
           \r[q1\u00ac\u000f^\u0082b/A\u0010\u0087\u00ff\u00e4k=\u00c8\u00d6\u001c\u007f
           \u00fb\u00db\u00da&\u00d9\u00c5\u00c4\u008a#\u00a0u\u0003J&\n\u0083
           \u00a0\u00e1.\u00ba\u00fd\u008a0s?\u00deg\u00d50\u0015\u00eb\u0091
           \u00b3E\u00c7\u0015O\u00f3r\u00e3`~8\u00b4\u00b5=\u0089U\u007f\u00fa\u0019"

Check this link for the easiest implementation of the GCD algorithm. I won't implement it, because Java has it out of the box, as part of the BigInteger class. Here is my code:

import java.math.BigInteger;
import java.security.MessageDigest;
import java.util.Arrays;

public class RSATest {
 private static final long MAX_ITER = 100000;
 private static final int MAX_TRY = 5;
 private static final int BLOCK = 128;

 // hash function used by OAEP deoceder
 private static byte[] hash(byte[] b) throws Exception {
  assert b.length == BLOCK/2;

  MessageDigest algo = MessageDigest.getInstance("SHA-512");
  algo.reset();
  algo.update(b);
  return algo.digest();
 }

 // converts a String to a BigIntteger
 // convertion is performed as if the String were 
 // in base 256
 public static BigInteger stringToInt(String str) {
  int sz = str.length();

  BigInteger ret = new BigInteger("0");
  BigInteger v256 = new BigInteger("256"); // the base
  BigInteger mul = new BigInteger("1");

  for (int i = sz - 1; i >= 0; --i) {
   int v = str.charAt(i);
   ret = ret.add((new BigInteger("" + v)).multiply(mul));
   mul = mul.multiply(v256);
  }

  return ret;
 }


 // a simple method for xor-ing to byte arrays
 private static byte[] xor(byte[] b, byte[] a) {
  assert b.length == BLOCK/2;
  assert b.length == a.length;

  byte[] ret = new byte[BLOCK/2];
  for (int i = 0; i < BLOCK/2; ++i) ret[i] = (byte) (a[i] ^ b[i]);
  return ret;
 }

 // decodes an OAEP array, google for OAEP padding
 private static byte[] oaepDecode(byte[] b) throws Exception { 
  assert b.length == BLOCK;

  byte[] first  = Arrays.copyOfRange(b, 0, BLOCK/2);
  byte[] second = Arrays.copyOfRange(b, BLOCK/2, BLOCK);
 
  byte[] r = xor(second, hash(first));
  byte[] m = xor(first,  hash(r));

  return m;
 }

 // converts a BigInteger into a String
 // if withOAEP is set to true, then also applies
 // OAEP decoding
 public static String intToString(BigInteger n, boolean withOAEP) 
     throws Exception {
  byte[] b_r_n = n.toByteArray();
  int b_sz = b_r_n.length;

  // apply OAEP decoding
  if (withOAEP) {
   if (b_sz > BLOCK) {
    // make sure we pass the right size, i.e. of one BLOCK
    b_r_n = Arrays.copyOfRange(b_r_n, b_sz - BLOCK, b_sz);
   }
   b_r_n = oaepDecode(b_r_n);
  }
  return new String(b_r_n);
 }

 // a simple decoder with the private key (d, n)
 public static void decode(BigInteger d, BigInteger n, String cipherText) 
     throws Exception {
  BigInteger cipherInt  = stringToInt(cipherText);
  BigInteger messageInt = cipherInt.modPow(d, n);

  // a simple note that if messageInt is a solution for the
  // above modulo congruence eq, then messageInt + k*n is also 
  // a solution

  for (int i = 0; i < MAX_TRY; ++i) {
   System.out.println("Try: " + i);
   System.out.println("Integer message: " + messageInt);
   System.out.println("String message (flat) = " + 
    intToString(messageInt, false));
   System.out.println("String message (oaep) = " + 
    intToString(messageInt, true));
   System.out.println();
   messageInt = messageInt.add(n);
  }
 }

 // this method attempts to decode the cipher by pretending 
 // it knows "p" which is a composition of "n", i.e. n = p*q
 public static void decode_with_p(long e, BigInteger n, String cipher, 
     BigInteger p) throws Exception {
  BigInteger q = n.divide(p);

  BigInteger phi = q.subtract(BigInteger.ONE).multiply(
     p.subtract(BigInteger.ONE));

  BigInteger E = new BigInteger("" + e);
  for (long k = 0; k < MAX_ITER; k++) {
   BigInteger r = phi.multiply(
    new BigInteger("" + k)).add(BigInteger.ONE);

   BigInteger[] qr = r.divideAndRemainder(E);
   if (qr[1].equals(BigInteger.ZERO)) {
    // remainder is ZERO
    System.out.println("Cycle: " + k);
    System.out.println("Try private key: " + qr[0]);
    decode(qr[0], n, cipher);
    System.out.println();
   }
  }
 }

 public static void main(String[] args) throws Exception {
  long e1 = 65537;
  BigInteger n1 = new BigInteger( 
   "592718383732377122410106984267855459479807503768946" +
   "605328456116093852954935746424599660398425081028346" +
   "005508211894335487221528999838842772667374160929852" +
   "573051680099378617005092405110706474184136037559125" +
   "038434888569799049915177291007255128504216646347052" +
   "74281314737938901139871448406073842088742598680079967");

  String cipher1 = 
   "J\u00c1R\u0090\u00e1\u00f4\u008b5My\u00f8\u00a1\u00f4>" +
   "\u00a2\u00c3\u0010\u00bd\u00eb\u00cc&\u007fb\u001aC$" +
   "\u001d\u00c5\u00b7\u00cdz\u00b7\u0017\u008a#9\u0012" +
   "\u0089\u00feao\u0019\u009c\u00eb\u00b0>\u0086\u009b" +
   "\u001d3~b0-u\u00fc\u0004!\rc\\\u00cb$\u0091\u009e" +
   "\u00a1N\u009d2\u00ff\u0019\u009a9vH.\u00d5\u00e7m" +
   "\u00a9m\u00ea^\u00d3T$\u00d7\u00d7\u0011\u0081\u00e4B" +
   "\u009b~\u008c $\u00a6K\u008a\u00dc`\u00b4\u009cu" +
   "\u00fb\u00c2\u0006\u00d1\u00bb\u00b9\u00a0\u008f\u00d2" +
   "\u00bc\u0002\u00f6#\u001f\u001dM\u00bb\u0098\u00f2" +
   "\u00a0\u009fO\u0080";

  long e2 = 65537;
  BigInteger n2 = new BigInteger( 
   "722162209295858740298002503411446285940493287510826" +
   "327939752381429703458019585940083215576976146078904" +
   "922080143847114340766243750345752066598033488377571" +
   "129629910281750410842883648532072455460838627134172" +
   "456428247653875773318287044412273565827235602914257" +
   "53389466410790421096831823015438162111864463275922441");

  String cipher2 = 
   ".\u00fd9\u008dc\u00da\u00f9o\u00f5Vl\u00fb\u0087\u00ed" +
   "\u00d5 \u00ee\u00cf\u0097~\u00d8T\u00f9.\u0018\u00b1" +
   "\u00d5n^\u00a0\rA\u00e0\u001d\u00d5\u00c8:D\u00c9" +
   "\u0014o\u00de\u00dbo\u00f9>)bc'a\u00a2\u008e\u00c1|" +
   "\u00dd\r[q1\u00ac\u000f^\u0082b/A\u0010\u0087\u00ff" +
   "\u00e4k=\u00c8\u00d6\u001c\u007f\u00fb\u00db\u00da&" + 
   "\u00d9\u00c5\u00c4\u008a#\u00a0u\u0003J&\n\u0083" +
   "\u00a0\u00e1.\u00ba\u00fd\u008a0s?\u00deg\u00d50\u0015" +
   "\u00eb\u0091\u00b3E\u00c7\u0015O\u00f3r\u00e3`~8\u00b4" + 
   "\u00b5=\u0089U\u007f\u00fa\u0019";

  // this is really quick
  BigInteger p = n1.gcd(n2);
  System.out.println("p = " + p);
  System.out.println();

  decode_with_p(e1, n1, cipher1, p);
  decode_with_p(e2, n2, cipher2, p);
 }
}

Execute it with the following command line:

java -ea RSATest > results.txt

Inside the garbage, within the results.txt file, you should notice the following:

String message (oaep) = What could go wrong: http://pastebin.com/hNz9gZbe
...
String message (oaep) = A real example: http://digitaloffense.net/tools/debian-openssl

To conclude, take care when you generate the keys for RSA encryption (and yes, go through this link)!

If you'd like to go through more such quests, try this course (a really nice one).