fuknut
• The turning point from classical crypto to modern crypto.
• Enabled secure communications over unsecured channels between two persons who didn’t previously share a common secret.
• Enabled the Internet.
• Encryption is now a mathematical formula, not just randomized permutations.
• The encryption key is different from the decryption key, but tightly related by a mathematical relation.
Public Key Cryptography
_____ _______ Problem
• Given a semiprime number, find its prime factors.
Prime Factorization
What algorithm:
• 1- Find a very large prime 𝑝
and a generator 𝑔
• Both 𝑝 and 𝑔 are public
• Alice chooses a random 𝑥 ∈ 1, 𝑝 − 1
and send 𝑔𝑥.
• Bob chooses a random y ∈ 1, 𝑝 − 1
and send 𝑔𝑦.
• Both compute (𝑔𝑦)𝑥 and (𝑔𝑥 )𝑦 = 𝑔𝑥𝑦
Diffie Hellman
A hard problem means that, there is no _____ time algorithm that can solve it.
polynomial
Algorithm Used to find GCD
Euclidean algorithm
___ can only be used for Key Exchange
DH
____ can be used for :
Encryption
Signatures
Key exchange
RSA
Name The following problem:
• Given 𝑎 and 𝑏, elements in a group 𝐺, find k such that
𝑎 = 𝑏𝑘
The main problem with Symmetric Crypto:
Key distribution
Extended Euclidean algorithm
• Shortest Vector Problem (SVP):
____ Problems
• Given a lattice 𝐿, find the shortest non-zero vector 𝑣 ∈ 𝐿.
• Learning with Errors (LWE):
• Given pairs of (𝑥, 𝑦) such that 𝑦 = 𝑓 𝑥 + 𝑒 for some error 𝑒.
13
what are lattice problems
The ___ algorithm :
• Proposed by NIST in 1991.
• A clever way to use prime fields ℤ𝑃 for public-key crypto
(not semiprime as used in RSA)
• FIPS PUB 186-5 (Draft in Oct. 2019), DSS will be no longer approved for new
signatures.
• However, it is the basis of the current Elliptic-Curve DSA.
what is DSA (digital signature algo)
The ___ algorithm is designed using 𝐺𝐹 (2^8) , where each element is 8 bits over the irreducible polynomial:
𝑥8 + 𝑥4 + 𝑥3 + 𝑥 + 1
AES
Name one algorithm where:
• Attacks against the Integer Factorization Problem don’t work here.
• Much shorter key size for equivalent level of security.
Elliptic-Curve Cryptography (ECC)
• The ___ of an element 𝑥 is the smallest positive integer 𝑣 such that
𝑥𝑣 ≡ 1 (𝑚𝑜𝑑 𝑝)
• If 𝑣 divides 𝑝 − 1, then there exists an element in ℤ𝑝 ∗
having ____ 𝑣.
order
DSA
In ____ ____(ℤ𝑃), also called 𝐺𝐹(𝑃), each element is a positive integer number < 𝑃 and every operation is done modulo a prime number 𝑃.
• We select 𝑃 as a prime Number to create a field that has a generator and a multiplicative inverse for each element.
Prime Fields
In DH key exchange:
___ ___ are when:
• Select only 𝑝 = 2𝑞 + 1, where 𝑞 is also a prime.
safe primes
In ___ ____ 𝐺𝐹(2𝑚), also called ℤ𝑃 𝑋 (mod 𝑓) , each element is a polynomial with degree < 𝑚 and every operation is done module an irreducible polynomial 𝑓.
• We select the modulus to be “irreducible” to create a field that has a generator and a multiplicative inverse for each element.
Binary (galois) fields
____ Problem is defined by:
• Find the eth roots of an arbitrary number, modulo N.
• Given (𝑁, 𝑒) and the ciphertext 𝐶 ≡ 𝑃^𝑒 𝒎𝒐𝒅 𝑁 , find 𝑃.
what is the RSA Problem
Name 1 cryptographic algorithm
• Input data and characters are converted into the coordinates (𝑥, 𝑦) of a
point. Each point is part of an ____ ____
with a new def. of addition (and multiplication), it formed a Group.
Elliptic-curve cryptography (ECC)
Name two cryptographic algorithms where:
• Input data and characters are converted into Bits.
Each bit is part of an internal state (128 bits or 1600 bits).
AES and SHA-3
what time of curve is :
• Not very secure:
• Only 8 points on the curve.
• Very simple structure.
Clock curve
• Can determine if a number in ℤ𝑝 is a square or not.
• For any generator 𝑔 in ℤ𝑝, ____ ____ (𝑔𝑥 ∈ ℤ𝑝) can immediately tell
if 𝑔𝑥 is square or not, i.e. if 𝑥 is odd or even, which is the LSB of our secret.
Legendre Symbol
Name 3 cryptographic algorithms where:
• Input data and characters are converted into Numbers.
Each number is part of a prime or semiprime field.
• DH, RSA and DSA