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). Putting 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 = 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;
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();
}
public static BigInteger stringToInt(String str) {
int sz = str.length();
BigInteger ret = new BigInteger("0");
BigInteger v256 = new BigInteger("256");
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;
}
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;
}
public static String intToString(BigInteger n, boolean withOAEP)
throws Exception {
byte[] b_r_n = n.toByteArray();
int b_sz = b_r_n.length;
if (withOAEP) {
if (b_sz > 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);
}
public static void decode(BigInteger d, BigInteger n, String cipherText)
throws Exception {
BigInteger cipherInt = stringToInt(cipherText);
BigInteger messageInt = cipherInt.modPow(d, n);
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);
}
}
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)) {
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";
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:
...
String message (oaep) = A real example: http:
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).