I have been playing with RSA lately, you know the encryption protocol where you generate two primes, multiply them, give the product away to be used for encryption by others and keeping the primes for yourself since they are needed for decryption (that was very simplified).
I have read that the largest known number to ever have been factorized was 768 bits long. Such a number looks like this (in hex):
6d733229f36b1fe086f39b5ae05d0155e7658480fe7c987fe5da51734b6b8c02
a7b6b22e5da0afc0867d7315405bddd9062da121a3b0b2663397ae8a65085d53
927279c1c330247ff20c2f1bd4b4f95375a74beefac29c519a8193e2614ffc19
For encryption to be safe for the next decades, keys that are 2048 or 4096 bits long are used. Or even longer.
One feature of RSA is that the output of encryption is never smaller than the size of the key (well, again, very simplified). So, imagine you want to encrypt 4-digit pin codes, one-by-one, using RSA with 1024-bit key, each pin code would be several hundred bytes, instead of just a few characters. For almost obvious reasons, you can not make a stream cipher of RSA or some other smart mode of operation to work around this problem (please let me know if I am wrong). This makes me want to use RSA with a small enough key to be secure enough for my purposes.
My questions
- What key sizes are trivial to break?
- What sizes require some qualified effort?
- How hard is it really to factorize big integers?
I found a tool called Yafu. It appears to be rather competent. It would require years of effort and advanced skills in math to write a better tool. For integers 320 bits and larger, Yafu requires GGNFS – a seriously very complicated piece of software that also hard to compile. Luckily there are nice windows binaries from Jeff Gilchrist. I also downloaded a binary version of Yafu for Windows. The examples below use Cygwin to have access to some Unix tools (bc, tr, openssl).
Generating a Prime product and factorizing it
There is a very nice JavaScript project for RSA. Set the bit size to whatever you want (I use 128 in this example), click generate, and obtain “Modulus”:
Modulus (hex): 81653c1536c42501a815431dac804899
Convert to upper case using tr:
$ echo 81653c1536c42501a815431dac804899 | tr '[:lower:]' '[:upper:]'
81653C1536C42501A815431DAC804899
Then use bc to convert to decimal:
$ bc -q
ibase=16
81653C1536C42501A815431DAC804899
171996052064283111843964589052488861849
quit
Finally, factorize using yafu:
$ echo "factor(171996052064283111843964589052488861849)" | ./yafu-x64.exe
06/14/14 13:24:28 v1.34.5 @ TOR, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.1.1
detected Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz
detected L1 = 32768 bytes, L2 = 6291456 bytes, CL = 64 bytes
measured cpu frequency ~= 3108.870930
using 20 random witnesses for Rabin-Miller PRP checks
===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
======= bbuhrow@gmail.com =======
======= Type help at any time, or quit to quit =======
===============================================================
cached 78498 primes. pmax = 999983
>>
fac: factoring 171996052064283111843964589052488861849
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 1000 iterations on C39
rho: x^2 + 2, starting 1000 iterations on C39
rho: x^2 + 1, starting 1000 iterations on C39
pm1: starting B1 = 150K, B2 = gmp-ecm default on C39
ecm: 30/30 curves on C39, B1=2K, B2=gmp-ecm default
starting SIQS on c39: 171996052064283111843964589052488861849
==== sieving in progress (1 thread): 624 relations needed ====
==== Press ctrl-c to abort and save state ====
546 rels found: 293 full + 253 from 2026 partial, (41408.50 rels/sec)
SIQS elapsed time = 0.0740 seconds.
Total factoring time = 0.2690 seconds
***factors found***
P20 = 14624642445740394983
P20 = 11760701343804754303
ans = 1
Now I wrote a little bash script that does everything:
#!/bin/bash
INTSIZE=$1
rm -f key.*
rm -f *.log
rm siqs.dat
BC_LINE_LENGTH=9999
export BC_LINE_LENGTH
openssl genrsa -out key.pem $INTSIZE
openssl rsa -in key.pem -noout -modulus | cut -f 2 -d '=' > key.hex
echo "ibase=16 ; $( cat key.hex )" | bc > key.dec
echo "factor($( cat key.dec ))" | ./yafu-x64.exe -threads 4
I am using yafu with default settings – very hard to imagine I can do anything better than the yafu author. For 320 bits and above, the GGNFS library is required. Performance for different sizes of integers to factorize (using the QuadCore Intel i5-2400 from the output above):
| Bits |
Time |
Notes |
| 128 |
0.28s |
| 160 |
0.33s |
| 192 |
1.86s |
| 224 |
8.02s |
| 256 |
52.6s |
| 288 |
265s |
| 320 |
3649s |
~30Mb Temp files |
| 352 |
9291s |
| 384 |
27261s |
~660Mb Temp files |
| 512 |
73 days |
http://lukenotricks.blogspot.se/2009/08/solo-desktop-factorization-of-rsa-512.html |
Well, this means that a normal Windows desktop computer can break 512 bit RSA within days or weeks. Below 512 bits, brute force is not much of a challenge, and using 256-bit RSA for encrypting short messages is (unfortunately, since it was what I ultimately wanted to explore) just ridiculous.
As keys get larger, more temp disk space is required, somewhere between 512-768 bits it gets seriously complex (I claim this, as a 768 bit integer is the largest to have been known to ever been factorized into two primes). You can read about General Number Field Sieves to get some background.
Not everyone is capable of extracting the Modulus integer from en encrypted file or network stream, installing Yafu, waiting for a little while and then use the two obtained primes to actually generate a fake certificate or actually decrypt anything. So, if you want to encrypt data to prevent your boss or your wife from reading it, you can probably use any key size you like – or why not use an encrypted zip file or an encrypted MS Word file?
If you have a skilled and motivated enemy, who are willing to put some effort into breaking your encryption, I would not use anything close to 512 bits. I assume the police, or FRA (in Sweden) or NSA can break 512 bit RSA within hours or faster when they need to.
I am not giving any sources for any of my claims here. I am not an expert in factorizing large-prime-products, and I am certainly not an expert in Quantum Computers. But as I understand it; 1024 bits should be fine, but perhaps in 10-20 years using even larger keys may make sense, and I don’t expect to see Quantum computers practically breaking real RSA keys in the next 50 years.
It is fascinating that a 128-bit AES key is completely beyond hope to brute force for any power on earth, while 128-bit RSA keys are worthless.
I now wonder, are there other asymmetric ciphers that are secure with significantly shorter keys than RSA?