Transcript Data encryption with big prime numbers

Data encryption with big
prime numbers
DANIEL FREEMAN, SLU
Old school codes
Full knowledge of the code is needed to both encrypt messages
and to decrypt messages.
The code can only be used between a small number of trusted people.
Public key encryption
If you buy something online, you need to send your credit card number to Amazon.
Your computer needs to be able to encrypt your credit card number.
Amazon does NOT want you to be able to decrypt other people’s credit card numbers.
Everyone needs to be able to encrypt but only Amazon should be able to decrypt.
We need a mathematical technique that is computationally very simple to evaluate, but is
extremely computationally difficult to invert.
Multiplication is easy, factoring is hard
Typing in the following into Wolfram Alpha
3568535685356853568535723 * 7564533681359827542555893
gives an output of
26994308385016394749558484505346578147056894665639
Typing in the following into Wolfram Alpha
factor 26994308385016394749558484505346578147056894665639
gives an output of
factor 26994308385016394749558484505346578147056894665639
Mod n
We think of x mod n as the remainder when x is divided by n.
1 ≡ 7 𝑚𝑜𝑑 3
2 ≡ 12 𝑚𝑜𝑑 5
0 ≡ 15 𝑚𝑜𝑑 5
More generally, x≡y mod n means that x and y have the same remainder when divided by n,
or that x-y is a multiple of n.
10 ≡ 7 𝑚𝑜𝑑 3
22 ≡ 12 𝑚𝑜𝑑 5
30 ≡ 15 𝑚𝑜𝑑 5
Modular exponentiation
31 ≡ 3 𝑚𝑜𝑑 5
32 ≡ 9 ≡ 4 𝑚𝑜𝑑 5
33
≡3∗
32
5 +23 +2
𝑚𝑜𝑑 5
5 +23 +2
𝑚𝑜𝑑 5
342 ≡ 32
≡ 32
≡ 3 ∗ 4 ≡ 12 ≡ 2 𝑚𝑜𝑑 5
≡ (32 )5 (32 )3 32 𝑚𝑜𝑑 5
34 ≡ 3 ∗ 33 ≡ 3 ∗ 2 ≡ 6 ≡ 1 𝑚𝑜𝑑 5
≡ 45 ∗ 43 ∗ 4 𝑚𝑜𝑑 5
⋮
≡ 4 𝑚𝑜𝑑 5
Fermat’s little theorem:
Let p be a prime number and let x be an integer that is not divisible by p. Then,
𝑥 𝑝−1 ≡ 1 mod p
or
𝑥 𝑝 ≡ x mod p
Key points of modular exponentiation
xm mod n
can be efficiently calculated by expressing the exponent m in binary.
Fermat’s little theorem:
Let p be a prime number and let x be an integer that is not divisible by p. Then,
𝑥 𝑝−1 ≡ 1 mod p
Euler’s theorem:
Let p and q be distinct prime numbers and let x be an integer that is not divisible by p or q. Then,
𝑥 (𝑝−1)(𝑞−1) ≡ 1 𝑚𝑜𝑑 𝑝𝑞
𝑥
More generally, if
𝑝−1 𝑞−1 +1
≡ 𝑥 𝑚𝑜𝑑 𝑝𝑞
m ≡ 1 mod (p-1)(q-1)
then
𝑥 𝑚 ≡ 𝑥 𝑚𝑜𝑑 𝑝𝑞
RSA encryption
Choose 2 large prime numbers p and q.
Calculate n=pq.
p and q should be so large that it is not computationally feasible to factor n.
n will be publicly shared, but p and q will be secret.
Choose a positive integer e which is relatively prime to (p-1)(q-1). e will be publicly shared.
Choose a positive integer d such that
ed ≡ 1 mod (p-1)(q-1)
d will be secret
Suppose someone wants to encrypt the integer x such that 1<x<n-1.
They encrypt x as the value y ≡ xe mod n
To decrypt, we exponentiate to the power d to get yd ≡ xed ≡ x mod n
RSA example
Choose p = 2498359
q = 5418341 p and q are just two big prime numbers
Calculate
n = pq = 2498359 * 5418341 = 13536961002419
Calculate
φ(n) = (p-1)(q-1) = 2498358 * 5418340 = 13536953085720
Choose e = 234234239 e was picked to be a prime number big enough to most likely not a factor of (p-1)(q-1)
Solve ed ≡ 1 mod (p-1)(q-1)
d = 9846393595559
Suppose you want to send the number x=432564456 to Amazon.
You calculate and send y=10021380275883 ≡ xe mod n
Amazon then calculates x ≡ yd mod n