Number Theory & Cryptography
Symmetric Key Cryptography
This topic has been covered before in:
One-Time Pad
This is one of the most secure ciphers known.
For this encryption scheme Alice and Bob share a random bit string
This key
Although is is very secure and fast to compute, Alice and Bob must share very long keys
One-Time Pad Encryption
-
To encrypt the message
, Alice computes: is the exclusive or (XOR) operation. -
Alice then sends
to Bob on any reliable communication channel. The communication is secure because is computationally indistinguishable from a random bit string.This relies highly on the fact that
was selected randomly.
One-Time Pad Decryption
Bob can easily decrypt the cipher-text
where 0 represents the all-zero string with the same length as
Number Theory
The following methods allow us to devise a solution for public key cryptography.
Divisibility
Given integers
If
Theorem: Let
- If
and then (transitivity). - If
and then for all integers and . - If
and then either or .
Prime Numbers and Composite Numbers
Integers that are not prime are composite.
Theorem: Let
The product
Greatest Common Divisor
Let
If
The definition of the GCD can be extended like so:
- If
, then . if and/or is negative. is undefined as there is no largest integer that divides 0.
Theorem: If
In other words, the greatest common divisor of
Function | Expression |
---|---|
Modulo Operator
For
This means that
Congruences
We can write this as:
In other words, if
as
Euclid’s Algorithm
Euclid’s algorithm is a method to fine the greatest common divisor of two integers
Theorem: Suppose
Euclid’s Algorithm Pseudo-Code
EuclidGCD(a, b)
Input:
Output:
while b != 0 do
(a, b) = (b, a mod b)
return a
If
Euclid’s Algorithm Example
We can display this algorithm in a table:
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|
412 | 260 | 152 | 108 | 44 | 20 | 4 | |
260 | 152 | 108 | 44 | 20 | 4 | 0 |
hence
Euclid’s Algorithm Time Complexity
For
This implies that, after the first time through the loop, the sequence
We can show that
Theorem: Let
arithmetic operations.
Extended Euclidean Algorithm
If
We can modify Euclid’s algorithm to fine these numbers
Extended Euclidean Algorithm Pseudo-Code
ExtendedEuclidGCD(a, b)
Input: Non-negative integers
Output:
if b = o then
return (a, 1, 0)
r = a mod b
q = floor(a / b) // Let q be the integers such that a = q * b + r
(d, j, k) = ExtendedEuclidGCD(b,r)
return (d, k, j - kq)
Extended Euclidean Algorithm Example
We can represent
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|
412 | 260 | 152 | 108 | 44 | 20 | 4 | |
260 | 152 | 108 | 44 | 20 | 4 | 0 | |
1 | 1 | 1 | 2 | 2 | 5 | * | |
152 | 108 | 44 | 20 | 4 | 0 | * | |
12 | -7 | 5 | -2 | 1 | 0 | 1 | |
-19 | 12 | -7 | 5 | -2 | 1 | 0 |
Note that
This produces the result of:
Public-Key Cryptography
A public-key cryptosystem consists of an encryption function
-
Both E and D are easy to compute for the following:
- It is computationally infeasible to derive D from E.
-
The knowledge of the encryption method gives no information about the decryption scheme. Anybody can send a private message to the hold of the function
, but only that person knows how to decrypt it.For this reason
is referred to as a one-way, or trapdoor, function.In this kind of encryption method
is made public and is kept private. -
The recipient of a message should be able to verify that it came from the sender, assuming that the sender is the only person who has a the private key.
This is referred to as digital signatures.
RSA
RSA Encryption
The main idea of the RSA method is as follows:
- Let
and denotes two large distinct prime numbers. - Let
and define . - We can then choose two numbers
and such that: and are relatively prime ( )-
We can use the Extended Eculidean algorithm to find
, given .
Assume that we have a message to send. We can split this message up into block of at most
The plain-text
RSA Decryption
Decryption of the received cipher-text
This is correct as for every integer
RSA Encryption Strength
Even knowing
Most cryptographers believe that breaking RSA required the computation of
As the ability to factor large numbers increases, we simple have to choose larger primes
RSA Time Complexity
Using fast exponentiation, the size of the operands is never more than
This leads to the following result:
Theorem: Let
Digital Signatures
RSA supports digital signatures. Suppose that Bob sends a message
Alice verifies the digital signature using the encryption function, by checking that:
Since only Bob knows the decryption function, this will verify that it was indeed Bob who sent the message.
Any person can use the encryption function as well to reconstruct the message
Fast Exponentiation
A possible bottleneck in the RSA algorithm is computing expressions of the form:
The naive approach is to calculate
We can do much better with an algorithm based on repeated squaring. For example, if we wanted to compute
If we are performing modular exponentiation, like in RSA, after each step we can find
Fast Exponentiation Pseudo-Code
FastExponentation(x, k, n)
Input: Integers
Output:
r = 1
t = x
while k != 0 do
if k is odd then
r = r * t mod n
t = t^2 mod n
k = floor(k / 2)
return r