Public Key crypto

Question 1

modular inverse (additive vs multiplicative)

Answer 1

ex: 5 mod 7

Multiplicative question: “what can we multiply 5 by to get 1 mod 7?” (both numbers must share GCD of 1)

https://www.youtube.com/watch?v=FnQNbFl72LY

Additive question: “What number can add to 5 mod 7 that will result in a value of 0?”

Question 2

primitve root check process

Answer 2

for given number p, choose number x.

Iterate x^n mod p (for n = 1 … n == p-1)

If all results are distinct and all results are less than p, the number is a primitive root.

https://www.youtube.com/watch?v=Ef6YcpmnIqs

EX: To check if 2 is a primitive root of 11:
2^1 mod 11 = 2
2^2 mod 11 = 4
2^3 mod 11 = 8
2^4 mod 11 = 5
2^5 mod 11 = 10
2^6 mod 11 = 9
2^7 mod 11 = 7
2^8 mod 11 = 3
2^9 mod 11 = 6
2^10 mod 11 = 1

Question 3

totients

Answer 3

Question 4

modular congruence

Answer 4

Congruence:
A == B mod(C)
means
A mod(C) = B mod(C)

For Example:
(26 mod 5 = 1) and (11 mod 5 = 1) so ….
(26 == 11 mod 5)

Question 5

c = 7^27 mod 30

Answer 5

using totient function,

c =7 ^{27mod ϕ(30)} mod 30

ϕ30 = ϕ10 * ϕ3

ϕ10 = 4

ϕ3 = 2

ϕ30 = 8

so…

c =7 ^{27mod 8} mod 30

c =7 ³ mod 30

c = 343 mod 30

c = 13

Question 6

theoretical basis for RSA

Answer 6

factoring a large number into two primes it very hard

Question 7

RSA key lengths in practice

Answer 7

1024, 2048, 4096

Question 8

RSA attributes

Answer 8

1. plaintext treated as an integer and must be smaller than the keylength
2. ciphertext block is the same as the key length
3. supports both public key encryption and digital signatures

Question 9

Why is RSA secure?

Answer 9

Factoring number at least 512 bits is very hard

Question 10

issues with normal RSA

Answer 10

1. deterministic mapping of plaintext -> ciphertext
2. some characters lik 0, 1, -1 are always the same
3. malleable on attacker side (can intercept and change ciphertext)

In practice random padding is prefixed to message. This addresses issues listed above

Question 11

Diffie Hellman Key Exchange

Answer 11

Question 12

Why is diffie hellman hard to break?

Answer 12

the exponent x is very hard to solve for

Question 13

limitations of diffie hellman

Answer 13

1. expensive exponentiation cycles that present DOS attack vulnerability (attacker requests a bunch of bogus key exchanges)
2. it cannot be used for anything other than key exchange
3. no authentication

Question 14

Bucket Brigade attack

Answer 14

Diffie hellman mand in the middle attack

1. Party A initiates a session with party B.
2. Malicious middle man C sends their bogus Y^a value to party B, andB thinks he received the real thing.
3. The malicious actor then sends A his own computed Y^b value.
4. Then the session is in fact between A and C
5. And session between B and C

Question 15

solution to bucket brigade attack

Answer 15

publish Y^a and Y^b values at a public, trusted site.

or

sign Y values when sending to the other party

Question 16

Alternative to RSA

Answer 16

ECC elliptic curve cryptography

(equal security for smaller bit size)

But not as thoroughly vetted as RSA