Public-Key Cryptography & RSA Flashcards
Private (Symmetric) Key
One key
sent to all parties through secure channels
new key when party leaves
all parties equal (so they can forge messages and claim they came from a different party)
Public (Asymmetric) Key
Two keys
public to encrypt and verify digital signatures
private to decrypt and digitally sign
parties aren’t equal (encryptor can’t decrypt
verifier can’t create digital signature)
useful for encryption/decryption and/or key exchange and/or digital signature
Relatively Prime
If a and b have a GCD of 1, they are relatively prime
doesn’t necessarily mean either are prime
GCD - Prime Factorization
One way to find GCD
find prime factorization of each number and check GCD
GCD - Euclid’s Algorithm
Another way to find GCD no factoring find larger number modulo smaller one find smaller one modulo result find prev result modulo new result until you get 0 second to last result is GCD
RSA
Ron Rivest, Adi Shamir, Len Adleman
Plaintext/Ciphertext blocks are integers between 0 and n
Size of n usually 1024 bits (309 decimal places)
n = p * q (p and q must be secret, prime, and can’
t equal each other)
When generating keys, e is usually 65537, 3, or 17 (BUT smaller e=simple attack)
(Cheat Sheet)
RSA - RSA Attacks - Factorization
d and m too hard and take too long to compute
n easiest to attack
if e, n, p, and q, known, can compute keys to encrypt/decrypt (d logically equivalent to e^-1 mod( p-1 * q-1 ) )
RSA - RSA Attacks - Timing
Get exact time hardware takes to decrypt something (depends on how many bits are 1 in d or e) to get feel for which bits should be set to what
RSA - RSA Attacks - Timing - Blinding
Multiply C by random number (C * r^e mod n) after encryption, so during “decryption” attacker will time wrong number
Real decryption is Mb * r^-1 mod n
RSA - RSA Attacks - Timing - Random Delay
Add random delay to exponentiation
RSA - RSA Attacks - Chosen Ciphertext
Replace real ciphertext with phony one and send to intended recipient
Get “message” from intended recipient and use it to derive the real message
Counter this with OAEP (pad M with psuedo-random bits)
DH
Create and exchange secret shit (like session keys)
Work if and only if both parties can be authenticated
Works because session key is derived the same by both parties
Works because even if p, primitive root, and public values are known, you can’t get private values or session key
(Cheat Sheet)
Primitive Roots
Given p > 1, there exists a primitive root a, that {a^j mod p | j = 1, 2, …, p - 1} = {1, 2, …, p-1}
DH - DH Attacks - Brute Force
Have to find discrete logarithm of one of the public keys (infeasible for large p)
DH - DH Attacks - Man in the Middle
Take public values Ya and Yb as they are sent, and replace them with Y1 (to A) and Y2 (to B)
Derive Ka and Kb
When B sends message with session key Kb, Decrypt with Kb, read, then encrypt with Ka so A can decrypt with Ka
Works if no one authenticates the origin of the public keys
