Transcript Pretty Good Privacy - New Mexico State University

Prime Numbers
• The Fundamental Theorem of Arithmetic
Prime Numbers and RSA
Euclidean algorithm Eudoxus of Cnidus
(about 375 BC),
•
•
•
•
•
•
function gcd(a, b)
if a = 0 return b
while b ≠ 0
if a > b a := a − b
else b := b − a
return a
Euclid’s algorithm: GCD
• The greatest common divisor of M and N is
the largest whole number that divides evenly
into both M and N
• GCD (6 , 15 ) = 3
• If GCD (M, N) = 1 then M and N are called
relatively prime.
• Euclid’s algorithm: method to find GCD (M,N)
Euclid’s algorithm
• M and N whole numbers.
• Suppose M ≤ N. If N is divisible by M then
GCD(M,N) = M.
• Otherwise, subtract from N the biggest
multiple of M that is smaller than N. Call the
remainder R.
• N=MK+R or R=MK-N. If Q divides into both M
and N then Q divides into R. So:
• GCD(M,N) = GCD (M,R).
• Repeat until R divides into previous.
Example: GCD (105, 77)
• 77 does not divide 105.
• Subtract 1*77 from 105. Get R=28
• 28 does not divide into 77. Subtract 2*28 from
77. Get R=77-56=21
• Subtract 21 from 28. Get 7.
• 7 divides into 21. Done.
• GCD (105, 77) = 7.
Example: GCD (105, 47)
• 47 does not divide 105.
• Subtract 2*47 from 105. Get R=11
• 11 does not divide into 47. Subtract 4*11 from
47. Get R=47-44=3
• 3 does not divide 11. Subtract 3*3 from 11.
R=2
• 2 does not divide 3. Subtract 2 from 3. R=1
• GCD (105, 47) = 1.
Exercise: find GCD (1234,121)
Relatively prime
• Two numbers M and N are called relatively
prime if GCD(M,N)=1.
Prime numbers
• A whole number is called prime if it is
relatively prime to every smaller whole
number.
Prime factorization theorem
• fundamental theorem of arithmetic :
• every natural number > 1 can be written as a unique
product of prime numbers.
• Example: 6936=2 x 2 x 2 x 3 x 17 x 17
• =2^3 x 3 x 17^2
• No other way of writing 6936 as a product of prime
powers
• practically proved by Euclid,
• first “ correct” proof in Disquisitiones Arithmeticae
by Gauss.
[GCD(6251,1473)=]
A.
B.
C.
D.
[1]
[3]
[7]
[11]
Large prime numbers
• Euclid: infinitely many prime numbers
• Proof: given a list of prime numbers, multiply
all of them together and add one.
• Either the new number is prime or there is a
smaller prime not in the list.
Euclid’s proof
• Consider any finite set of primes. Multiply all of them
together and add 1 (see Euclid number). Call this Q
• Dividing Q by any of these would give a remainder of 1.
• So Q is not divisible by any number in this list.
• Any non-prime can be decomposed into a product of primes,
• Either Q is prime itself, or there is a prime number in the
decomposition of Q that is not in the original finite set of
primes.
• Either way, there is at least one more prime that was not in
the finite set we started with. This argument applies no
matter what finite set we began with. So there are more
primes than any given finite number.
Infinitude of primes
• 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 …
• list of prime numbers
Testing for prime numbers
• Is 97 a prime number?
• How about 111?
• How about 12345678987654321?
Computers can factor small prime
numbers
Primality test
• A primality test is an algorithm for
determining whether an input number is
prime.
• As of 2008, factorization is a computationally
hard problem, whereas primality testing is
comparatively easy.
• elliptic curve primality test O((log n)^6),
• Based on believed, but unproven properties
• 2002: Agrawal, Saxena and Kayal :
• AKS primality test, Õ((log n)^6)
RSA 200
• RSA-200 =
27997833911221327870829467638722601621070446786955
42853756000992932612840010
76093456710529553608560618223519109513657886371059
54482006576775098580557613
579098734950144178863178946295187237869221823983
• RSA-200 =
35324619344027701212726049781984643686711974001976
25023649303468776121253679
423200058547956528088349 ×
79258699544783330333470858414800596877379758573642
19960734330341455767872818
152135381409304740185467
How long to factor RSA 200?
• If a k-digit number is the product of two primes
• No known algorithm can factor in polynomial time, i.e., that
can factor it in time O(k^p) for some constant p.
• There are algorithms faster than O((1+ε)^k) i.e., subexponential.
• For a quantum computer, Peter Shor discovered an algorithm
in 1994 that solves it in polynomial time O(N^3) and O(N)
memory.
• In 2001, the first 7-qubit quantum computer became the first
to run Shor's algorithm. It factored the number 15
• GNFS: O(2^(N^(1/3))
Racing Mathematicians
• German Federal Agency for Information Technology Security
(BSI) team
• record for factorization of semiprimes ( RSA Factoring
Challenge )
• On May 9, 2005, factored RSA-200, a 663-bit number (200
decimal digits), using the general number field sieve.
• …later: RSA-640, a smaller number containing 193 decimal
digits (640 bits), on November 4, 2005.
• Both factorizations required several months of computer time
using the combined power of 80 AMD Opteron CPUs.
[The number 2*3*5*7*11+1=2311 is
prime]
A. True
B. False
There are lots of primes known to man
• Prime number theorem: the number of
primes less than or equal to N is on the order
of N divided by log N.
• http://en.wikipedia.org/wiki/Prime_number_t
heorem
Largest known prime
• 243,112,609 − 1.
An example
•
•
•
•
•
gcd(1071,1029)
=gcd(1029,42) (42= 1071 mod 1029
=gcd(42,21) (21= 1029 mod 42)
=gcd(21,0) (0= 42 mod 21)
=21: since b=0, we return a
Run time of Euclidean (O(N^2)).
Red: fast, blue: slow
RSA
The RSA encryption algorithm
•
•
•
•
•
•
•
N=PQ (product of two primes)
Φ(N) = (P-1)(Q-1)
Encryption key: 1<E<φ(N) such that
GCD(E , φ) = 1
Decryption key: D such that
DE ≡ 1 mod (φ)
M< φ
Encryption/Decryption
• C=MD mod (N)
• R=CE mod (N)
• CLAIM: R=M (the original message)
Short digression: modular arithmetic
• A ≡ B mod (C)
• Means that B is the remainder when C is divided
into A
• For example, 13 ≡ 1 mod (12)
• If it is 3:30 now then in 13 hours it will be 4:30.
• Shorthand: B=mod(A,C)
• Arithmetic:
• mod (MN, C)=mod(mod(M,C) x mod(N,C), C))
Laws of exponents
Regular exponents Modular exponents
(ab)c = ac bc
mod((ab)c ,m)=
mod(mod (ac ,m) mod (bc ,m), m)
ab+c=ab ac
mod(ab+c,m)=
mod(mod (ab ,m) mod (ac ,m), m)
(ab)c = abc
mod((ab)c ,m)=
mod((mod (ab ,m))c, m)
Examples
• mod((13)25 ,12)=
• mod((mod (13 ,12))25, 12)=
• mod(125, 12)= mod(1, 12)= 1
•
•
•
•
mod((14)25 ,12)=
mod((mod (14 ,12))25, 12)=
mod(225, 12)= mod(mod(24, 12)6 x mod(2,12), 12)=
mod(mod(4, 12)5 x2, 12)=mod(8 , 12)=8
Proof of RSA
•
•
•
•
•
•
C=ME mod (N)
R=CDmod (N) = (MD mod (N))E mod (N) =
(MDE mod (N))
DE ≡ 1 mod (N)
(M1 mod (N)) =M (since M< N)
Fermat’s little theorem: aP-1 ≡ 1 mod (P)
Plaintext to numbers
- A B C D E F G H I J K L MN O P Q R S T U V WX Y Z
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
Plaintext message
• Kill Bill
numerical version
• Kill Bill == 11 09 12 12 00 02 09 12 12
• M=110912120002091212
• Note: M<φ so may need to send message
in pieces, e.g. one letter at a time
Example
•
•
•
•
•
•
•
11 09 12 12 00 02 09 12 12
N = 5 x 7 =35
Φ=4x6=24
E=11 then GCD (E, Φ)=1
D=11 then DxE=121=5x24+1
So DxE≡1 mod 24
In this case decryption is just the inverse of
encryption because E=D. Generally note true.
- A B C D E F G H I J K L MN O P Q R S T U V WX Y Z
000000000011111111112222222
012345678901234567890123456
001101022001021113022203133
018290682456374513240182901
EXERCISE
• Use the cipher table above to decrypt the
following ciphertext into plain text:
• 0603012020100230 00 32040303 00 281020
301521 00 14153222100210 00 182120 00
09151420 00 24201511 00 200230041422
Solution:
• Flattery will get
you nowhere, but
don't stop trying
•
•
•
•
•
•
Simple; multiply numbers
Difficult: factor numbers.
example 34537 x 99991=3453389167 (easy)
M=1459160519 = A xB
Find A and B (difficult)
Computer: check primes up to square-root (roughly 38000).
How long to factor large products?
what if the number to be factored is not ten digits, but rather
400 digits?
square-root : 200 digits.
lifetime of universe: approx. 10^{18} seconds.
If computer could test one trillion factorizations per second,
in the lifetime of the universe it could check 10^{30}
possibilities.
But there are 10^{200} possibilities.
RSA outline
•
•
•
•
•
•
•
•
•
•
•
•
•
•
find two huge prime numbers, p and q (about 200 digits) (private key),
N=pq public key.
Baby prime example
p=23 and q=41
pq = (23)(41) = 943, the ``public key’’.
E: encryption key
E is relatively prime to (p-1)(q-1) = (22)(40) = 880,
E=7 is ok as public key
To encode the message number M=35. :
C = M^e (mod N) = 35^7 (mod 943) =64339296875 (mod 943) = 545
The number C=545 is the encoding of M that is sent.
D: decryption key
ed = 1 { mod} (p-1)(q-1):
D=503 works, since 7*503 = 3521 = 4(880) + 1
Why decoding is “easy”
•
•
•
•
•
•
•
•
•
•
•
•
•
Must calculate C^D (mod N) = 545^{503} (mod 943).
503 = 256 + 128 + 64 + 32 + 16 + 4 + 2 + 1 so
545^{503} = 545^{256+128+64+32+16+4+2+1}
= 545^{256}545^{128}… 545^1.
(mod 943) all the exponents that are powers of 2.
For example, 545^2 ( mod 943) = 545*545 = 297025 (mod 943) = 923
Square again: 545^4 (mod 943) = (545^2)^2 ( mod} 943)
= 923*923 = 851929 (mod 943) = 400, and so on.
We obtain the following table:
545^1 (mod 943) = 545
545^2 (mod} 943) =…= 18
545^{256} (mod 943) = 324
So …545^{503} (mod 943) = 324*18*215*795*857*400*923*545 (mod
943) = 35=M !
Memory efficient modular exponentiation:
Montgomery reduction
•
•
Memory-efficient method
Makes use of: given two integers a and b, the following two equations are
equivalent:
•
•
•
C = ab mod m
C = ( (a mod m)x (bmod m) ) mod
The algorithm is as follows:
•
•
•
•
•
•
1. Set c = 1, e' = 0.
2. Increase e' by 1.
3. Set c =b mod m
4. If e' <e, goto step 2. Else, c contains the correct solution to c = b^e mod m
in every pass through step 3, c = b^(e’) mod m holds true.
In summary, this algorithm basically counts up e' by ones until e' reaches e, doing a
multiply by b and the modulo operation each time it adds one
The example b = 4, e = 13, and m = 497 is presented again. The algorithm
passes through step 3 thirteen times:
* e' = 1. c = (1 * 4) mod 497 = 4 mod 497 = 4.
* e' = 2. c = (4 * 4) mod 497 = 16 mod 497 = 16.
* e' = 3. c = (16 * 4) mod 497 = 64 mod 497 = 64.
* e' = 4. c = (64 * 4) mod 497 = 256 mod 497 = 256.
* e' = 5. c = (256 * 4) mod 497 = 1024 mod 497 = 30.
* e' = 6. c = (30 * 4) mod 497 = 120 mod 497 = 120.
* e' = 7. c = (120 * 4) mod 497 = 480 mod 497 = 480.
* e' = 8. c = (480 * 4) mod 497 = 1920 mod 497 = 429.
* e' = 9. c = (429 * 4) mod 497 = 1716 mod 497 = 225.
* e' = 10. c = (225 * 4) mod 497 = 900 mod 497 = 403.
* e' = 11. c = (403 * 4) mod 497 = 1612 mod 497 = 121.
* e' = 12. c = (121 * 4) mod 497 = 484 mod 497 = 484.
* e' = 13. c = (484 * 4) mod 497 = 1936 mod 497 = 445.
The final answer for c is therefore 445
requires O(e) multiplications to complete.
the computation time decreases by a factor of at least O(e) in this method.
An efficient method: the right-to-left binary algorithm
•
third method: combines previous method and “exponentiation by squaring”
•
convert exponent e to binary notation. That is, e can be written as:
•
e = a_0 x 1 + a_1 x 2^1 + a_2 x 2^2 +… +a_N x 2^N
•
“length” of e is N bits. a_i = 0 or 1
•
b^e = (b^0)^(a_0) x (b^1)^(a_1) x…x (b^N)^(a_N)
•
So
•
C= (b^0)^(a_0) x (b^1)^(a_1) x…x (b^N)^(a_N) mod M
RSA history
• Algorithm described in 1977 by Ron Rivest, Adi Shamir, and Leonard
Adleman at MIT;
• Clifford Cocks, a British mathematician working for the UK intelligence
agency GCHQ, described an equivalent system in an internal document in
1973. His discovery, however, was not revealed until 1997 due to its topsecret classification, and Rivest, Shamir, and Adleman devised RSA
independently of Cocks' work.
• MIT was granted U.S. Patent 4,405,829 for a "Cryptographic
communications system and method" that used the algorithm in 1983.
The patent would have expired in 2003, but was released to the public
domain by RSA on 21 September 2000.
Pretty Good Privacy
PGP
• Based on “public key” cryptography
• Binds public key to user name or email address
• Authentication: “digital signature” used to verify
identity of sender
• integrity checking: used to detect whether a
message has been altered since it was completed
• Encryption: based on RSA/DSA
• Decryption based on public key
• Web of trust: third party vetting
Zimmerman, 1992
• As time goes on…
• you accumulate keys from other “trusted”
parties.
• Others each choose their own trusted parties.
• everyone gradually accumulates and distributes
with their key certifying signatures from others
• Expectation: anyone receiving it will trust at least
one or two of the signatures.
• emergence of a decentralized fault-tolerant web
of confidence for all public keys.
• Any agency wanting to read PGP messages would
probably use easier means than standard
cryptanalysis,
• e.g. rubber-hose cryptanalysis or black-bag
cryptanalysis i.e. installing some form of trojan
horse or keystroke logging software/hardware on
the target computer to capture encrypted
keyrings and their passwords.
• The FBI has used this attack against PGP.
• such vulnerabilities apply to any encryption
software.
• Criminal investigation of Zimmerman
• PGP encryption found its way outside the US.
• Cryptosystems using keys > 40 bits were considered munitions by US
export regulations;
• PGP keys >= 128 bits.
• Feb 1993: Zimmermann targeted by US Govt for "munitions export
without a license".
• Penalties … were substantial.
• Zimmermann challenged these regulations in a curious way.
• Published PGP source code as hardback book (MIT Press)
• To build: buy the $60 book, scan pages using an OCR program, GNU C
Compiler. PGP would thus be available anywhere in the world.
• Export of munitions restricted; export of books is protected ( First
Amendment).
• US export regulations regarding cryptography remain in force, but were
liberalized substantially …. PGP … can be exported internationally except
to 7 specific countries and a named list of groups and individuals.
Mathematical Cryptography
• William S. Jevons,” The Principles of Science: A
Treatise on Logic and Scientific Method,” (1890s)
• observed many situations where 'direct' operation is
“easy,” but ‘inverse' operation ‘hard’.
• Example: encryption is easy; decryption is hard.
• Jevons Ch 7: multiplication of integers is easy, finding
(prime) factors of product is hard.
• Jevons anticipated RSA Algorithm for public key
cryptography
The future of cryptography?
• As of 2005, the largest number factored by a general-purpose
factoring algorithm was 663 bits long (see RSA-200), using a
state-of-the-art distributed implementation. RSA keys are
typically 1024–2048 bits long. Some experts believe that
1024-bit keys may become breakable in the near term
(though this is disputed); few see any way that 4096-bit keys
could be broken in the foreseeable future. Therefore, it is
generally presumed that RSA is secure if n is sufficiently large.
If n is 256 bits or shorter, it can be factored in a few hours on a
personal computer, using software already freely available.
Keys of 512 bits (or less) have been shown to be practically
breakable in 1999 when RSA-155 was factored by using
several hundred computers. A theoretical hardware device
named TWIRL and described by Shamir and Tromer in 2003
called into question the security of 1024 bit keys. It is
currently recommended that n be at least 2048 bits long.
Is RSA safe?
• In 1994, Peter Shor published Shor's
algorithm, showing that a quantum computer
could in principle perform the factorization in
polynomial time. However, quantum
computation is still in the early stages of
development and may never prove to be
practical.