1 of 21

Cryptography

By:

Dr. Mohammad Shoab

Week 9 & 10

2 of 21

Prime Numbers

  • A prime number is the one which has exactly two factors, which means, it can be divided by only “1” and itself. But “1” is not a prime number.

​

Example of Prime Number

3 is a prime number because 3 can be divided by only two number’s i.e. 1 and 3 itself.

3/1 = 3

3/3 = 1

In the same way, 2, 5, 7, 11, 13, 17 are prime numbers.

​

2

Cryptography

Department of Computer Science

3 of 21

Composite Numbers

  • A composite number has more than two factors, which means apart from getting divided by the number 1 and itself, it can also be divided by at least one integer or number. We don’t consider ‘1’ as a composite number.

Example of Composite Number

12 is a composite number because it can be divided by 1, 2, 3, 4, 6 and 12. So, the number ‘12’ has 6 factors.

12/1 = 12

12/2 =6

12/3 =4

12/4 =3

12/6 =2

12/12 = 1

3

Cryptography

Department of Computer Science

4 of 21

Modular Arithmetic

  • Modular arithmetic is a system of arithmetic for integers, which considers the remainder.

​

  • In modular arithmetic, numbers "wrap around" upon reaching a given fixed quantity (this given quantity is known as the modulus) to leave a remainder.

​

  • Modular arithmetic is often tied to prime numbers

​

4

Cryptography

Department of Computer Science

5 of 21

Modular Arithmetic

CS555

5

  • Modular Arithmetic is one of the main tools provided by number theory
    • The quotient of n divided by m is , where m and n are positive integers
    • The remainder of this division is called 'n mod m'
    • So, the following holds:

​

where the first term is the quotient and the second the remainder.

Cryptography

Department of Computer Science

6 of 21

Modular Arithmetic

CS555

6

  • Another way of putting this is:
    • Given any positive integer n and any integer m, if we divide m by n, we get an integer quotient, q, and integer remainder, r, that obey the following relationship:

​

​

    • The remainder, r, is often referred to as a residue of m modulo n, and is the smallest non-negative integer that differs from m by a multiple of n.

For example,

Cryptography

Department of Computer Science

7 of 21

Modular Arithmetic

CS555

7

  • Two integers, a and b are said to be congruent (denoted by ) if:

​

that is, "a is congruent to b modulo m"

  • Alternatively, in arithmetic modulo m, a and b are equivalent if their difference, (a - b), is a multiple of m; that is, m | (a - b)
  • The set of integers Zm = {0,1, ... m - 1} form the complete set of residues modulo m -- there are only m different integers, mod m
  • The operation a mod m denotes the residue of a, such that the residue is some integer from 0 to m - 1. This operation is known as a modular reduction.
    • Example:

Cryptography

Department of Computer Science

8 of 21

Modular Arithmetic

8

  • Congruence is an equivalence relation -- that is, it satisfies:

​

​

​

​

  • Finding the smallest non-negative integer to which k is congruent modulo n is called reducing k modulo n

Cryptography

Department of Computer Science

9 of 21

Modular Arithmetic

9

  • We can also add and subtract congruent elements without losing congruence:

​

​

​

  • Multiplication also works:

​

Cryptography

Department of Computer Science

10 of 21

Modular Arithmetic

10

  • Modular arithmetic is like ordinary arithmetic. It is:
    • commutative (for addition and multiplication)

a + b = b + a

    • associative

(a + b) + c = a + (b + c)

and

    • distributive

a(b + c) = (ab) + (ac)

and

(b + c)a = (ba) + (ca)

Cryptography

Department of Computer Science

11 of 21

Modular Arithmetic

CS555

11

  • A very important property of modular arithmetic is:
    • Reducing each intermediate result modulo m yields the same result as doing the entire calculation, and then reducing the result to modulo m:

​

​

​

​

​

    • This means that we can do modular arithmetic without worrying about whether we will exceed some large arithmetic bound -- so such calculations can be done on computers, even for large integer values.

​

Cryptography

Department of Computer Science

12 of 21

Modular Arithmetic

CS555

12

  • Cryptography uses modular arithmetic a great deal, because:
    • Calculating discrete logarithms and square roots mod n can be hard problems.
    • It's easier to work with on computers, because it restricts the range of all intermediate values and results
      • For a k-bit modulus, n, the intermediate results of any addition, subtraction, or multiplication will not exceed 2k bits in length.
      • We can perform modular exponentiation without generating huge intermediate results
      • Arithmetic operations, mod 2, are natural for computers, because of the equivalence of addition with XOR, and multiplication with AND, etc.

Cryptography

Department of Computer Science

13 of 21

Vanilla Key Exchange (Diffie-Hellman)

  • The Diffie-Hellman key exchange was the first widely used method of safely developing and exchanging keys over an insecure channel.

​

  • It allows two parties who have not previously met to securely establish a key which they can use to secure their communications.

CS555

13

Cryptography

Department of Computer Science

14 of 21

Diffie-Hellman

  • For the sake of simplicity and practical implementation of the algorithm, we will consider only 4 variables, one prime P and G (a primitive root of P) and two private values a and b.
  • P and G are both publicly available numbers. Users (say Alice and Bob) pick private values a and b and they generate a key and exchange it publicly. The opposite person receives the key and that generates a secret key, after which they have the same secret key to encrypt.

​

CS555

14

Cryptography

Department of Computer Science

15 of 21

CS555

15

Example

Cryptography

Department of Computer Science

16 of 21

Computational Diffie–Hellman Assumption

  • The computational Diffie–Hellman (CDH) assumption is a computational hardness assumption about the Diffie–Hellman problem. 

​

  • The CDH assumption involves the problem of computing the discrete logarithm in cyclic groups. The CDH problem illustrates the attack of an eavesdropper in the Diffie–Hellman key exchange protocol to obtain the exchanged secret key.

�

CS555

16

Cryptography

Department of Computer Science

17 of 21

Cont…

CS555

17

Cryptography

Department of Computer Science

18 of 21

The End

18

Cryptography

Department of Computer Science

19 of 21

Exercise

Q1. Explain prime numbers.

Q2. Explain composite numbers.

Q3. What is modular arithmetic?

Q4. What is vanilla key exchange?

Q5. Explain Diff-Hellman with example.

Q6. What is Computational Diffie–Hellman Assumption?

​

19

Cryptography

Department of Computer Science

20 of 21

Q7. A prime number is the one which has exactly

  1. One factor
  2. Two factors
  3. Three Factors
  4. N Factors

Q8. Modular arithmetic is a system of arithmetic for integers, which considers the.

  1. Prime number
  2. Composite number
  3. Reminder
  4. None of the above

Q9. We can also add and subtract congruent elements without losing.

  1. Congruence
  2. Linearity
  3. Security
  4. None of the above

​

Cryptography

Department of Computer Science

21 of 21

Q10. We can perform modular exponentiation without generating huge.

  1. Final results
  2. Initial results
  3. Output
  4. Intermediate results

Q11. The Diffie-Hellman key exchange was the first widely used method of safely developing and exchanging keys over an.

  • Insecure channel
  • Secure channel
  • Network
  • Communication channel

Q12. The CDH assumption involves the problem of computing the discrete logarithm in.

  • Arrays
  • Lists
  • Stacks
  • Cyclic group

Cryptography

Department of Computer Science