Now I'm going to use the 'real' oracle -- OpenSSL. The code is mostly the same, but it calls openssl executable and also it can use RSA public key in PEM file format. See this and this.
Now tests on random RSA keys. 512 bits, 1024, 2048, 4096 -- all fast. Within one hour on AMD Ryzen 5 3600 6-Core.
512 bits:
... Valid padding. new m_lower/m_upper 0x20172f14a7...5461672109 log2=497.0 0x20172f14a7...546167210a log2=497.0 m_lower: 00000000: 00 02 01 72 F1 4A 75 D1 41 E6 0D ED 35 33 E7 3E ...r.Ju.A...53.> 00000010: 68 14 B4 DB BE 64 07 6C C5 00 48 65 6C 6C 6F 2C h....d.l..Hello, 00000020: 20 77 6F 72 6C 64 21 20 48 6F 6C 61 2C 20 6D 75 world! Hola, mu 00000030: 6E 64 6F 21 20 47 75 74 65 6E 20 54 61 67 21 09 ndo! Guten Tag!. m_upper: 00000000: 00 02 01 72 F1 4A 75 D1 41 E6 0D ED 35 33 E7 3E ...r.Ju.A...53.> 00000010: 68 14 B4 DB BE 64 07 6C C5 00 48 65 6C 6C 6F 2C h....d.l..Hello, 00000020: 20 77 6F 72 6C 64 21 20 48 6F 6C 61 2C 20 6D 75 world! Hola, mu 00000030: 6E 64 6F 21 20 47 75 74 65 6E 20 54 61 67 21 0A ndo! Guten Tag!. diff 1 Found! upper: 00000000: 00 02 01 72 F1 4A 75 D1 41 E6 0D ED 35 33 E7 3E ...r.Ju.A...53.> 00000010: 68 14 B4 DB BE 64 07 6C C5 00 48 65 6C 6C 6F 2C h....d.l..Hello, 00000020: 20 77 6F 72 6C 64 21 20 48 6F 6C 61 2C 20 6D 75 world! Hola, mu 00000030: 6E 64 6F 21 20 47 75 74 65 6E 20 54 61 67 21 0A ndo! Guten Tag!. With PKCS#1 1.5 padding removed: 00000000: 48 65 6C 6C 6F 2C 20 77 6F 72 6C 64 21 20 48 6F Hello, world! Ho 00000010: 6C 61 2C 20 6D 75 6E 64 6F 21 20 47 75 74 65 6E la, mundo! Guten 00000020: 20 54 61 67 21 0A Tag!. calls_to_oracle 18544
Only 18k calls to openssl!
RSA 1024 bits:
... With PKCS#1 1.5 padding removed: 00000000: 4C 6F 72 65 6D 20 69 70 73 75 6D 20 64 6F 6C 6F Lorem ipsum dolo 00000010: 72 20 73 69 74 20 61 6D 65 74 2C 20 63 6F 6E 73 r sit amet, cons 00000020: 65 63 74 65 74 75 72 20 61 64 69 70 69 73 63 69 ectetur adipisci 00000030: 6E 67 20 65 6C 69 74 2C 20 73 65 64 20 64 6F 20 ng elit, sed do 00000040: 65 69 75 73 6D 6F 64 20 74 65 6D 70 6F 72 20 69 eiusmod tempor i 00000050: 6E 63 69 64 69 64 75 6E 74 20 75 74 20 6C 61 62 ncididunt ut lab 00000060: 6F 72 65 2E 2E 2E 0A ore.... calls_to_oracle 140747
Only 140k calls to openssl.
2048 bits: 51k calls to openssl! 4096 bits: 66k calls!
But not 256-bits. My AMD spent ~5 hours on it. ~1.1 million calls. What's the problem? Why it's that slow? It's because the smaller the space, the lesser probability of zero byte residing somewhere. The larger the key, the larger the space, and that probability is much higher. The original Bleichenbacher's paper has all the info about probability calculations.
Now the video. Decrypting 2048-bit RSA message. I hope, this can be used in some 'c00l l33t hax0r' movie if fancier font is picked, maybe greenish:
You see, you can use my Python script to decrypt something real. As long as remote server would return the 'invalid padding' error. Despite the fact that all this you read was written by a non-professional crypto-noob like me.
Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.