Public Key Cryptography Flashcards
What modular arithmetic is reversible and used for public key cryptography
modular additive inverse
What is the modular multiplicative inverse of 2 numbers =?
1
What basic mathematical premise is used for RSA?
factoring a very large number (512-bit or larger) into 2 primes is very difficult
RSA has a requirement on plaintext relative to the key. what is it?
The plaintext must be smaller than the key. The plaintext is converted to integers and its integer form must be smaller than the key, which can be 1024-4096 bits.
Describe all components of RSA algorithm (N, p, q, e, d) and what is the encryption/decryption equations?
N= pq st p, q are primes
totient(N) = (p-1)(q-1)
d*e mod totient(N) = 1 where d & e are relatively prime to totient(N)
public key is and private key is
message length of M < length of N
encrypt message M: C=M^e mod N
decrypt M: M = C^d mod N
What equations are used for digital signatures using RSA
signature = encrypt message equation verification = decrypt message equation
What are RSA shortcomings? What can be done to ameliorate these?
same ciphertext for a given message
for certain m, the ciphertext is always -1,0,or 1
an attacker can append the cipher-ed text in a predictable way to mess w the ciphered message
The fix: add padding to the beginning of m before encrypting it
Diffie Hellman is an allows for what type encryption between 2 parties?
Shared secret key
How does Diffie Hellman work?
public #’s q = prime number >300 digits and alpha = a prime root of q
To share a secret key, User 1 picks a random integer Xa and sends to User 2: Y1 = alpha^Xa mod q. Likewise, for User 2 picks Y2 and sends a likewise equation to User1.
The shared secret key is s = Y2^Xa mod q
What mathematical difficulty that Diffie Hellman exploits?
it’s difficult to compute the discrete log of one of the publicly exchanged messages (Y1 or Y2) because q is so large
What’s the benefit of Diffie Hellman
No secret keys are transmitted
Drawbacks of Diffie Hellman
- An attacker could ask to exchange lots of Y2 and cause the victim to compute lots of exponential (expensive) operations leading to Denial of Service
- Doesn’t encrypt messages
- No authentication of users, so can’t do digital signatures like RSA can
4.
What’s an attack to Diffie Hellman?
Bucket Brigade Attack (Man in Middle)
in which the shared keys that are computed are with the attackers between 2 Users because there’s no authentication
The fix: Users publish the public messages or User’s sign their own public Y keys
Name some other public key algorithms
- Digital Signature Algorithm (DSA) based on SHA-1
- Elliptic-Curve cryptography (same security of RSA but can be stronger and newer, so not as confident at ECC than RSA)
