Scribd
Upload
14 views16 pages

Crypto Important

The document discusses cryptography concepts like prime numbers, modulo operators, and Euclid's algorithm. It provides examples of computing modulo, finding the greatest common divisor of numbers using Euclid's algorithm, and using the extended Euclidean algorithm to find multiplicative inverses in modular arithmetic.

Uploaded by

Shobhit Tiwari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views16 pages

Crypto Important

The document discusses cryptography concepts like prime numbers, modulo operators, and Euclid's algorithm. It provides examples of computing modulo, finding the greatest common divisor of numbers using Euclid's algorithm, and using the extended Euclidean algorithm to find multiplicative inverses in modular arithmetic.

Uploaded by

Shobhit Tiwari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 16

Cryptography & Network Security

Subject Code: KCS074

Pankaj Kumar
Assistant Professor

Department of Computer Science & Engineering


Pranveer Singh Institute of Technology, Kanpur, India

November 6, 2023
Prime Number

• A prime number p is an integer greater than 1 with only two positive


divisors, i.e., 1 and itself. Therefore it’s entire set of divisors (i.e. its
factors) consist only of four integers ±1 and ±p.
• It can be seen that 1 is not a prime number.

• Prime numbers are of the utmost importance to certain cryptographic


algorithms and most of the techniques used will not work without them.

Pankaj Kumar November 6, 2023 2/16


Modulo Operator

Find the result of the following operations:


1 27 mod 5 (Solution: 2)
2 −16 mod 14 (Solution: Remainder is -2. After adding the modulus,
the result is 12 (additive inverse of -16 mod 14)).

Pankaj Kumar November 6, 2023 3/16


Modulo Operator

Set of residue:
• The modulo operation creates a set, which in modular arithmetic is
referred to as the set of least residues modulo n, or Zn .
• Zn = {0, 1, 2, ...(n − 1)}
• Z2 = {0, 1}
• Z7 = {0, 1, 2, 3, 4, 5, 6}

Pankaj Kumar November 6, 2023 4/16


Modulo Operator

Congruence:
• To show that two integers are congruent, we use the congruence oper-
ator ≡. For example, we write:
• 4 ≡ 11 mod7
• 3 ≡ 26 mod23

Pankaj Kumar November 6, 2023 5/16


Modulo Operator

Modular Properties:
• (a + b) mod n = {(a mod n) + (b mod n)} mod n
• (a − b) mod n = {(a mod n) − (b mod n)} mod n
• (a × b) mod n = {(a mod n) × (b mod n)} mod n

Pankaj Kumar November 6, 2023 6/16


Modulo Operator

Inverse:
• Additive inverse (relative to addition operation):
• In modular arithmetic, each integer has an additive inverse.
• The sum of an integer and its additive inverse is congruent to 0 modulo
n, i.e., in Zn , two numbers a and b are additive inverses of each other
if
(a + b) ≡ 0 modn

Pankaj Kumar November 6, 2023 7/16


Modulo Operator

• Multiplicative inverse (relative to multiplication operation): In


modular arithmetic, an integer may or may not have a multiplicative
inverse. When it does, the product of the integer and its multiplicative
inverse is congruent to 1 modulo n.
• In Zn , two numbers a and b are the multiplicative inverse of each other
if (a × b) ≡ 1 mod n.
• Example 1: Find the multiplicative inverse of 8 in Z10 .
• Solution: There is no multiplicative inverse because gcd(10, 8) = 2 ̸=
1. In other words, we cannot find any number between 0 and 9 such
that when multiplied by 8, the result is congruent to 1.
• Example 2: Find all multiplicative inverses in Z10 .
• Solution: There are only three pairs: (1, 1), (3, 7) and (9, 9). The
numbers 0, 2, 4, 5, 6, and 8 do not have a multiplicative inverse.
Pankaj Kumar November 6, 2023 8/16
Euclid’s Algorithm: Finding GCD

Pankaj Kumar November 6, 2023 9/16


Euclid’s Algorithm: Finding GCD

Remark: When gcd(a, b) = 1, we say that a and b are relatively prime.

Pankaj Kumar November 6, 2023 10/16


Euclid’s Algorithm

• Example: Find the GCD of 25 and 60.

• The solution is 5, i.e., gcd(25,60)=5.


Pankaj Kumar November 6, 2023 11/16
Extended Exclidean Algorithm

• The extended Euclidean algorithm finds the multiplicative inverses of


b in Zn when n and b are given and gcd(n, b) = 1.
• The multiplicative inverse of b is the value of t after being mapped to
Zn .
• Given two integers a and b, we often need to find other two integers,
s and t, such that:
s × a + t × b = gcd(a, b).
• The extended Euclidean algorithm can calculate the gcd(a, b)and at
the same time calculate the value of s and t.

Pankaj Kumar November 6, 2023 12/16


Extended Exclidean Algorithm

Pankaj Kumar November 6, 2023 13/16


Extended Exclidean Algorithm

• Example 1: Find the multiplicative inverse of 11 in Z26 .

• The gcd(26, 11) is 1; the inverse of 11 is -7 or 19.

Pankaj Kumar November 6, 2023 14/16


Extended Exclidean Algorithm

• Example 2: Find the multiplicative inverse of 23 in Z100 .

• The gcd(26, 11) is 1; the inverse of 23 is -13 or 87.

Pankaj Kumar November 6, 2023 15/16


Thank You!

Pankaj Kumar November 6, 2023 16/16

You might also like