Flashcards
Vanilla RSA
Cards in this deck (9)
- 1RSA KeyGen
- 2RSA Encrypt
- 3RSA Decryptc^d === m (mod n)
- 4How to ensure RSA is a cryptosystem?Step 2 Key Gen Multiply Quick
Step 4 key gen mod(o(n) quick
Step 5 key gen attacker shouldn't be able to get d from e,n since 4 is fast they can get d fas from o(n) and therefore p and q so factorising N should be slow
Step 2 of Encrypt exponentiate quick - 5How to multiply fast?Represent q in binary and double: 2^0 * p = p
2^1 * p = p + p (one addition etc.)
Then add using pq = (2^i0*p) + ... _+ (2^ik * p) - 6How to exponentiate fast?CCompute m^2i (mod n) by repeat squaring:
m^2^0 === m ( mod n)
m^2^1 === m^2 *mod n
Then m^e (mod n) === m^2i0 * .... * m^2ik (mod n) - 7Solve x (mod 17*11) given x = 4 (mod 17) and x = 3(mod 11)With the factorization of N use the Euclidena algorithm to find a and b.
CRT says that x = bcm + a (1 - cm) === a (mod m)
For x = 5 (mod 29) and x - 12 (mod 101) then c = 5, d = 29, m = 101 and n = 12 - 8Examples of invalid keysAny factors of o(n) as they can't be inverted
- 9How to do 2047*7879 quick?2047 = 2^11 - 1
Double 7879 11 times then - 1
Information
- Description
- Cryptography Flashcards on Vanilla RSA, created by Philip Masters on 12/01/2020.
- Created by
- Philip Masters
- Views
- 0
- Rating