Asymmetric Cryptography

Question 1

How does the encryption process work in asymmetric cryptography?

Answer 1

The person’s public key should be used to encrypt the message, since only the person has the private key to decrypt and access its content.

Question 2

How does the message signing process work in asymmetric cryptography?

Answer 2

When the person wants to sign a message and the others want to confirm that the message was really signed by that person, it is necessary to encrypt with the person’s private key and then the other can decrypt and confirm with his/her public key.

Question 3

In which mathematical problem the asymmetric algorithms used to be based on?

Answer 3

The Knapsack problem (problema da mochila).

Question 4

In which mathematical problem the RSA algorithm is based on?

Answer 4

Factorization problem.

Question 5

In which mathematical problem the Diffie-Hellman and El-Gamal algorithms are based on?

Answer 5

Discrete logarithm problem

Question 6

Explain the gcd recursion theorem.

Answer 6

∀ a, b ∈ Z + : gcd(a, b) = gcd(b, a MOD b)

Question 7

Proof the gdc recursion theorem.

Answer 7

Step 1: ->
gcd(a, b) divides both a and b
-> it also divides any linear combination of them.

If we choose (a - a / b × b), this is equal to a MOD b,
so gcd(a, b) | gcd(b, a MOD b)
It means “gdc(a,b) is divided by gdc(b, a MOD b)”

Step 2:
so gcd(b, a MOD b) | gcd(a, b)
It means “gcd(b, a MOD b) is divided by gcd(a, b)”

Question 8

Explain the Euclidean Algorithm.

Answer 8

int Euclid(int a, b)
{ if (b = 0) { return(a);}
{ return(Euclid(b, a MOD b);} }

Question 9

What does the algorithm ExtendedEuclid computes?

Answer 9

The algorithm ExtendedEuclid given a, b computes d, m, n such that:
d = gcd(a, b) = m × a + n × b

Question 10

What does the Euclid theorem says?

Answer 10

If a prime divides the product of two integers, then it divides at least one of the integers:

p | (a × b ) ⇒ (p | a) ∨ (p | b)

Question 11

What does the fundamental theorem of arithmetic says?

Answer 11

Factorization into primes is unique up to order.

Proof: suppose two different factorizations (not only reordering) of n

n = p1 * p2 * p3 * … * pn
= q1 * q2 * q3 * … * qn

pick p1, by applying the euclidean theorem, there exist at least one qi that is divisible by pq. Reorder the q’s multiplications to be the factor q1 the part divisible by p1. It means that q1 and p1 are divisible by p1. Since both are primes, they have to be equal. So we can divide
by p 1 and we have that n / p 1 has a non-unique factorization.

Question 12

What does the Euler theorem says?

Answer 12

Let n and b be positive and relatively prime integers, i.e. gcd(n, b) = 1 ⇒ b^[ Φ(n) ]≡ 1 mod n

Question 13

What does Φ(n) means?

Answer 13

Φ(n) denote the number of positive integers less than n

and relatively prime to n.

Question 14

What does the Chinese Remainder Theorem says?

Answer 14

Let m 1 , …, m r be positive integers that are pairwise relatively
prime, i.e. ∀ i ≠ j: gcd(m i , m j ) = 1. Let a 1 , …, a r be arbitrary
integers.
Then there exists an integer a such that:
a ≡ a 1 mod m 1
a ≡ a 2 mod m 2
…
a ≡ a r mod m r
Furthermore, a is unique modulo M := m 1 × … × m r