n. Attack: because m ^ e < n then m = e-th root of c - p and q are not close primes. Attack: [[http://en.wikipedia.org/wiki/Fermat%27s_factorization_method | Fermat's factorization method]] def isqrt(n): x = n y = (x + n // x) // 2 while y < x: x = y y = (x + n // x) // 2 return x def fermat_factorization(N): a= isqrt(N) + 1 b2 = a*a - N while ( isqrt(b2) * isqrt(b2) - b2 != 0): a = a+1 b2 = a * a - N p = a - isqrt(b2) q = N / p if N != p *q: print "ERROR" return (0,0) return (p,q) - the message m is not encrypted using multiple public keys (#keys >= exponent). Attack example with exponent e = 3 and three public keys: c_flag1 = 0x21447c68f7b8a50bb1b85926f8db0d701b22a1d3f6f0346a83f4ffe3200205464ebd6a81252ac3cc252b920d6aefe3f300a164170bed6350ad6eb0fec595ef6b1a418fd67e853f76f2dea0a6b0a944559b5fa3fc2486e7f902fad2a0204dd73431b317819db8d6deeb301eba2e6bab1882707bc9d23e7618098b782154acde60L N1=127817843211733301505391824852464526713868683036869679914961355029587642439569421998232218330454582274690231975096419091273284982360770747508661250648133769232398929391627257277458468900785771317425651993276401829154454081922888125598647830550609238688264656644624824681727457711772686355239337013973824606617 c_flag2 = 0x7bba3c18705aff9c4f37d629e0241bb0ece5535dc9b5fa489cadc3082f675968fa4823fb209276c3da6c3e4fdd483233b8d985c3f65c843b197bb87171b91c8ea8d4fd08ce170336bd6ba5b27b477dd8b705501cf7ed5a31c91c5d7b2b3a9f1b97ea3b8b516adb2587b2731c2e401db8d0c2bbba754c97a1b426abf71666b29cL N2=102312914669701184087785390508966486652650119346006737061430481585509906827632939664906326724953393589527364036533787280035874678806866587465771600520687921882709584622092422396871928636879427367277570505632172456295537428117155062337559726327735397525508629957065168526315421070154740561587029595816876543137 c_flag3 = 0x96d411149c82e2aaa932155e8e116903c38f68a264b6015f04bdefa8b545000a10336cd288e246738ed09d6cbe49b3744930f5879f15c916abdee6b8e0234ed7b644be53acc7624d3b468df53d0b26597d9bf08628de9eadbfbad62c6a3423c3a4686fd466da0ccb762369b59f951de958f3330148d2771f1ab96e248ebdb28L N3=153152611218368384815040988787287534260086509588355776722157123311265084942048534623765557956560823595285314466222805844576492199421004781433017863950091752928385956540212336689177084769911428394250702214757176582730230125407833851112154328630450046743714533572386395118136429699085866787958143655847127308313 flag_cubed = crt( [N1, N2, N3], [c_flag1, c_flag2, c_flag3] ) flag = root3rd(flag_cubed) print hex(flag)[ 2 : -1 ].decode("hex") #prints "______________ key:{RSA_isn't_so_great_after_all?!} ______________" # reference: picoCTF 2013 * Sometimes not even the public key is known (except for maybe its bitlength) but a chosen plaintext attack can be mounted. Attack example for recovering the public key #known values: key_bitlength ; exponent #plaintext is in hex format (0x414243 etc) plaintext1 = get_random_plaintext(key_bitlength - 2) plaintext2 = get_random_plaintext(key_bitlength - 2) plaintext1_e = pow(plaintext1, exponent) plaintext2_e = pow(plaintext2, exponent) ciphertext1 = get_cipher(plaintext1) ciphertext2 = get_cipher(plaintext2) delta1 = plaintext1_e - ciphertext1 delta2 = plaintext2_e - ciphertext2 gcd = fractions.gcd(delta1,delta2) for i in range(2,1000): if gcd % i == 0: gcd = gcd / i n = gcd * Another situation arises if the attacker has a decryption oracle but a certain ciphertext c is forbidden from being decrypted. In this case the attacker can ask for the decryption of a derivative key c' = c * r^e (mod n). Because m1^e * m2^e = (m1 * m2) ^ e (mod n) and c = m ^ e mod (n) it follows that c' = (m * r) ^ e mod(n). The received decryption is m*r and r^(-1) is easily obtainable. m * r * r^(-1) = m, the original message * Other attacks: Wiener, Coppersmith, Timing attack, Power Attack, Faults Attack, [[http://www.hri.res.in/~kalyan/lecture2.pdf | Pollard's p and rho ]] * Papers on attacks: * {{:rsa_attacks.pdf|A Survey of Cryptanalytic Attacks on RSA}} * [[http://eprint.iacr.org/2013/026 | RSA private key reconstruction from random bits using SAT solvers ]] === El Gamal=== * Algorithm * Assumptions and attacks ===Elliptic curves=== * Algorithm * Assumptions and attacks * Paper on attacks {{:10.1.1.132.6034.pdf| Attacking the Elliptic Curve Discrete Logarithm Problem}}