Topics for midterm are everything bout crypography including this week.
midterm is next monday in class. He will give access code when we do midterm. it will be a canvas quiz in lockdown browser. 34 questions, most of them are concepts. some very few are scenario based questions. lockdown browser, there is a trial quiz, you need to do it before you come to the midterm
open book exam, you are allowed to print paper notes.
no internet, no ai, no cellphone.
lowest scored lab will be dropped 2 lowest scored quizzes will be dropped
Today is about RSA Encryption
The first public key cryptsystem invented by rivest, shamir, and adleman any bit size is OK Bit size of the modulus used to create public and private keys
the size is not comparable between AES and RSA
512 was standard when it was released 2048 or 4096 are standard now
based on prime numbers and factoring
KeyGen(): Randomly pick two large primes, p and q done by picking random numbers and then using a test to see if the number is probably prime Compute N = pq N is usually between 2048 bits and 4096 bits long Choose e: requirement: e is not a factor of (p-1)(q-1) requirement: 2 < e < (p-1)(q-1)
compute d = e^-1 mod ( p-1 ) (q - 1) 1 = (d * e) mod (p-1)(q-1) Algorithm: extended Euclid’s algorithm Public key: N and e Private key: d
Example: randomly pick two large primes, p and q p = 3 q = 7
Compute N = pq N = P * q = 21 Choose e: e = 5 ( not a factor of 2 * 6 = 12 )
compute the inverse: d = e^-1 mod (p-1)(q-1)
d = 5 since d* e mod (p1)(q-1) = 5 * 5 mod (2 * 6) = 1 public key: N = 21 and e = 5 private key d = 5
Enc(e,N,M): output: M^e mod N public key
Dec(d,C): Output: C^d mod N C^d mod N = (M^e)^d mod N
d is private key
Example: Enc(e,N,M) M = 12 e = 5 N = 21
C = 12^5 mod 21 = 3
Dec(d,C): Output C^d mod N c = 3, d = 5 , n = 21 M = 3^5 mod 21 = 243 mod 21 = 12
M^ed mod N = M mod N
RSA Encryption: Security RSA Problem: Given N and C = M^e Mod N, it is hard to find M
no harder than the factoring problem if you can factor N, you can recover d, because 1 = (d* e) mod (p - 1)(q-1) and N = p * q
A brute force attack is basically trying to factory the public key into two prime numbers ( this is also what gets weaker if we get powerful quantum computers )
Current best solution is to factor N, but unknown whether there is an easier way
raw rsa is deterministic, so it is not ind cpa secure. we need some source of randomness to throw in there.
sending the same message encrypted with different public keys also leaks information. m^0a mod Na, m^0b mod Nb m^0c mod Nc Small m and e leaks information
if e is 1, plaintext didnt change in encryption at all.
- e is usually small ( 16 bits ) and often constant (3, 17, 65537)
side channel: a poor implementation that leaks information the time it takes to decrypt a message depends on the message and the private key this attack has been successfully used to break rsa encryption in openssl result: we need some randomness
Optimal asymmetric encryption padding ( OAEP ) A variation of RSA that introduces randomness. different from “padding” used for symmetric encryption, OAEP is used to add randomness instead of dummy bytes idea: add randomness and structure to the plaintext before encryption.
the randomness go in the plaintext, hes showing a blue slide now.
Key size in RSA Encryption Typical RSA key sizes are 1024 or 2048 or 4096 bits. That number is the number of bits in the modulus, i.e. N = p * q. For each there will be a pair of primes roughly 512 bits or 1024 bits or 2048 bits, depending on the key size picked. Those primes are chosen by some random process.
Hybrid Encryption: Issues with public key encryption: notice: we can only encrypt small messages because of the modulo operator notice: there is a lot of math, and computers are slow at math result: asymmetric doesn’t work for long messages Hybrid Encryption: encrypt data under a randomly generated key K using symmetric encryption, and encrypt K using asymmetric encryption.
alice wants to send a message to bob alice chooses / generates a random symmetric key K Alice computes C1 = Enc(K,M) and sends it to Bob ( Symmetric encyrption ) Alice computes C2 = Enc(pub_bob, K) and sends it to Bob ( aymmetric encryption ) Bob receives both messages, uses his private key to decrypt C2 and get K Bob then uses K to decrypt C1 and get M
digital signatures: asymmetric cryptography is good because we dont need to share a secret key digital signatures are the asymmetric way of providing integrity / authenticity to data
public key signatures: only the owner of the private key scan sign messages with the private key
everybody can verify the signature with the public key
KeyGen() → PK, SK: Generate a public private keypair, where PK is the verify ( public ) key and the SK is the signing ( secret ) key
KEyGen(): same as rsa encryption public key n and e private key d
sign(d, M) compute sig = H(M)^d mod N
verify(e, N, M, sig) verify that H(m) (triple =) sig^e mod N = (H(M)^(d* e) mod N
If you want to sign a message M: first hash M