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 = m^e (mod n). Cipher text is decrypted in the following way m = c^d (mod n). Putting all these together m^e⋅d ≡ m (mod n) and if m and n are co-prime, then m^e⋅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 = 59271838373237712241010698426785545947980750376894660532845611609385295493574642459966039842508
1028346005508211894335487221528999838842772667374160929852573051680099378617005092405110706474184136
0375591250384348885697990499151772910072551285042166463470527428131473793890113987144840607384208874
2598680079967
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 = 7221622092958587402980025034114462859404932875108263279397523814297034580195859400832155769761
460789049220801438471143407662437503457520665980334883775711296299102817504108428836485320724554608
386271341724564282476538757733182870444122735658272356029142575338946641079042109683182301543816211
1864463275922441
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 decoder
 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
 // conversion 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).