kb:crypto:asym

Asymmetrical ciphers

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

El Gamal

Algorithm
Assumptions and attacks

Elliptic curves

Algorithm
Assumptions and attacks
Paper on attacks Attacking the Elliptic Curve Discrete Logarithm Problem

Table of Contents

Asymmetrical ciphers

RSA

El Gamal

Elliptic curves