Number Theory

Question 1

What are the benefits of number theory?

Answer 1

1. Key Exchange & Secure Channels to establish a secure channel against eavesdropping.
2. Public-key Encryption to encrypt a message with public key.
3. Digital Signatures to sign a message electronically
4. Zero-knowledge. Proofs of Knowledge to prove knowledge of a secret without disclosing the secret

Question 2

What is a ring group? Which properties establish that Zm forms a ring group?

Answer 2

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

Question 2

What is an abelian group? What properties establish that Zm forms an abelian group?

Answer 2

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

Question 3

17 in Z_{12} is?

Answer 3

5

Question 4

33(mod 13) is?

Answer 4

7

Question 5

6 + 13 (mod 7) is?

Answer 5

5

Question 6

-6 . 15 (mod 7) is?

Answer 6

1

Question 7

gcd(18,24), gcd(12,32)

Answer 7

6, 4

Question 8

Whats the formula for Bezouts identity? what is it used for?

Answer 8

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

Question 9

what can we use the euclidean algorithm to compute and whats the formula?

Answer 9

• 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

Question 10

What are the steps to compute extended euclidean algorithm?

Answer 10

1. Compute gcd(x,y)
2. Store all intermediary states d_i = x_i a_i + y_i b_i
3. Backtrack; substitute for the remainders d_i
   - Write as linear combination of x and y which is ax + by = gcd(x,y)

Question 11

Whats the extended euclidean algorithm for gcd(1776, 987)?

Answer 11

3 = (-5)1776 + 9(987)

sagemath: xgcd(1776,987) : (3, -5, 9)

Question 12

Whats the formula for multiplicative modular inverse?

Answer 12

x.y -= 1 (mod N)

Question 13

5^(-1) in Z_17?

Answer 13

y = 7
sagemath: xgcd(5 , 17) : (1, 7, -2)

Question 14

How do we know if x has a multiplicative inverse modulo N?

Answer 14

if gcd(x, N) = 1

Question 15

How do you compute modular inverses using the extended euclidean algorithm?

Answer 15

ax + bN = 1 = gcd(x, N)

Question 16

What does it mean for two numbers to be coprime?

Answer 16

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

Question 17

What is a cyclic group? give an example of a cyclic group

Answer 17

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.

Question 18

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)

Answer 18

→ a = b + kN for some k
→ a = b (mod N)
→ N | (a-b)

Question 19

Which of the following congruences are fulfilled?
→ 13 = 27 (mod 37)

→ 11 = 49 (mod 39)

→ -11 = 28 (mod 39)

→ 13 = 124 (mod 37)

Answer 19

→ -11 = 28 (mod 39)

→ 13 = 124 (mod 37)

Question 20

What is the greatest common divisor gcd(7302, 9354)?

Answer 20

6

Question 21

True or false: Two numbers x and y are coprime if and only if the gcd(x, y) = 1.

Answer 21

true

Question 22

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.

Answer 22

→ 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.

Question 23

What is the multiplicative inverse of x=17 modulo 231

Answer 23

68
sagemath xgcd(17, 231) is (1, 68, -5)

Question 24

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.

Answer 24

→ 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. ✅

Question 25

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?

Answer 25

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)