Asymmetrical ciphers

RSA

Initialisation Algorithm
- Choose p and q two prime numbers of similar bit length
- n = p * q (the public key or modulus)
- phi(n) = (p-1) * (q-1) (totient function)
- Choose exponent e such that gcd(e, phi(n) ) = 1 (common values include 3, 65537)
- Private key d = modular_inverse( e, phi(n) )
Encryption / Decryption
- c = m ^ e (mod n)
- m = c ^ d (mod n)

Assumptions and attacks

Public key is of sufficiently large bit length. Attack: brute force factorization (Cryptool has several efficient algorithms)
Factorization is unknown. Attack: database lookup at http://www.factordb.com
m ^ e > n. Attack: because m ^ e < n then m = e-th root of c

p and q are not close primes. Attack: 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:

rsa_attack1.py

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, Pollard's p and rho
Papers on attacks:
- A Survey of Cryptanalytic Attacks on RSA
- RSA private key reconstruction from random bits using SAT solvers