Number Theory Flashcards
What are the benefits of number theory?
- Key Exchange & Secure Channels to establish a secure channel against eavesdropping.
- Public-key Encryption to encrypt a message with public key.
- Digital Signatures to sign a message electronically
- Zero-knowledge. Proofs of Knowledge to prove knowledge of a secret without disclosing the secret
What is a ring group? Which properties establish that Zm forms a ring group?
A ring group is a set of numbers which addition and multiplication are well behaved
Properties:
Addition and multiplication is closed, commutative, associative, 0 is an additive identity, 1 is a multiplicative property. Additive inverse of any a in Zm is m-a, the distributive property
What is an abelian group? What properties establish that Zm forms an abelian group?
An abelian group is a groupin which the result of applying thegroup operationto two group elements does not depend on the order in which they are written.
Properties:
Addition is closed, commutative, associative, 0 is an additive identity, Additive inverse of any a in Zm is m-a
17 in Z_{12} is?
5
33(mod 13) is?
7
6 + 13 (mod 7) is?
5
-6 . 15 (mod 7) is?
1
gcd(18,24), gcd(12,32)
6, 4
Whats the formula for Bezouts identity? what is it used for?
For all non-zero x,y in Z, there exists a,b in Z, such that a.x + b.y = gcd(x,y)
used for computing multiplicative inverses
what can we use the euclidean algorithm to compute and whats the formula?
- computing gcd
- Key observation:Compute q =[x/y] w/ remainder r=x mod y
= y.q +r
If d divides both y and r; then it also divides x.
If d divides both × and y, then it also divides r.
gcd(x,y) = gcd(y,r) so basically (y, x mod y) until y is zero
What are the steps to compute extended euclidean algorithm?
- Compute gcd(x,y)
- Store all intermediary states d_i = x_i a_i + y_i b_i
- Backtrack; substitute for the remainders d_i
- Write as linear combination of x and y which is ax + by = gcd(x,y)
Whats the extended euclidean algorithm for gcd(1776, 987)?
3 = (-5)1776 + 9(987)
sagemath: xgcd(1776,987) : (3, -5, 9)
Whats the formula for multiplicative modular inverse?
x.y -= 1 (mod N)
5^(-1) in Z_17?
y = 7
sagemath: xgcd(5 , 17) : (1, 7, -2)
How do we know if x has a multiplicative inverse modulo N?
if gcd(x, N) = 1
How do you compute modular inverses using the extended euclidean algorithm?
ax + bN = 1 = gcd(x, N)
What does it mean for two numbers to be coprime?
Two numbers are coprime if their greatest common divisor (gcd) is 1. In other words, x is invertible in Z N if gcd(x,N)=1
What is a cyclic group? give an example of a cyclic group
A cyclic group is a type of group that can be generated b) repeatedly applying the group operation (g) to a single element, known as a generator. The elements of the group are the powers of g up to g^(p-2), which will generate all the elements of (Zp)* when p is prime.
Which statements are equivalent for a congruence modulo N?
→ a = b + kN for some k
→ a = b (mod N)
→ (b-a) | N
→ N | (a-b)
→ a = b + kN for some k
→ a = b (mod N)
→ N | (a-b)
Which of the following congruences are fulfilled?
→ 13 = 27 (mod 37)
→ 11 = 49 (mod 39)
→ -11 = 28 (mod 39)
→ 13 = 124 (mod 37)
→ -11 = 28 (mod 39)
→ 13 = 124 (mod 37)
What is the greatest common divisor gcd(7302, 9354)?
6
True or false: Two numbers x and y are coprime if and only if the gcd(x, y) = 1.
true
When does a multiplicative inverse of an integer x exist modulo N?
-> When gcd(x, N) = 1.
-> When x and modulus N are coprime.
-> When N is divisible by x.
-> When x > N.
→ When gcd(x, N) = 1.
→ When x and modulus N are coprime
It’s important to realize that coprimality between x and a modulus N is a necessary and sufficient criterion for the multiplicative inverse of x under modulus N to exist.
What is the multiplicative inverse of x=17 modulo 231
68
sagemath xgcd(17, 231) is (1, 68, -5)
What properties do we expect from a key exchange between two parties Alice and Bob?
The session key K is indistinguishable from a random number.
The session K is completely unguessable by an adversary.
The adversary cannot compute the session key from the transcript.
An adversary cannot impersonate Alice or Bob in the key exchange.
Both Alice and Bob obtain the same session key K.
→ The session key K is indistinguishable from a random number. ✅
→The session K is completely unguessable by an adversary. ✅
→ An adversary cannot impersonate Alice or Bob in the key exchange. ❌
While this would be desirable, the standard definitions of key exchange do not exclude man-in-the-middle attacks.
→ The adversary cannot compute the session key from the transcript. ✅
→ Both Alice and Bob obtain the same session key K. ✅
Consider two parties Alice and Bob attempting a Diffie-Hellman key exchange in a group setup with p = 1013 and g = 3. Alice chooses her secret a randomly as a=924. Bob chooses his secret b randomly as b=405. What is the joint session key K?
The correct transcript is developed as follows:
A = g^a = 3^924 (mod 1013) = 92 - Public key of Alice
B = g^b = 3^405 (mod 1013) = 693 - Public key of Bob
K = A^b = 92^405 = 253 = 693^924 = B^a (all mod 1013)
sagemath:
A = (3^924) % 1013
B = (3^405) % 1013
session_key1 = A^405 % 1013
session_key2 = B^924 % 1013
print(“A: “, A)
print(“B: “, B)
print(session_key1)
print(session_key2)
