## 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 = 59271838373237712241010698426785545947980750376894660532845611609385295493574642459966039842508102834600550821189433548722152899983884277266737416092985257305168009937861700509240511070647418413603755912503843488856979904991517729100725512850421664634705274281314737938901139871448406073842088742598680079967
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 = 72216220929585874029800250341144628594049328751082632793975238142970345801958594008321557697614607890492208014384711434076624375034575206659803348837757112962991028175041084288364853207245546083862713417245642824765387577331828704441227356582723560291425753389466410790421096831823015438162111864463275922441
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;
}

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();
}
}

// 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(

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).