Public Key Cryptography
Copyright By PowCoder代写 加微信 powcoder
Is it possible to communicate with encryption without having a shared secret key known in advance?
symmetric key crypto
public key cryptography
requires sender, receiver know shared secret key
radically different approach [Diffie- Hellman76, RSA78]
Q: how to agree on key in first place (particularly if they have never met)?
sender, receiver do not share a secret key
Typical problem in the Internet
decryption key private (known only to receiver)
encryption key public (known to all)
Public key cryptography
Figure 7.7 goes here
Public key encryption algorithms
Two inter-related requirements:
needd ()ande ()suchthat
dB(eB(m)) = m
need public and private keys
.. fordB()ande ()
RSA: Rivest, Shamir, Adleman algorithm
RSA: Choosing keys
1. Choose two large prime numbers p, q.
(e.g., 1024 bits each)
2. Compute n = pq, z = (p-1)(q-1)
3. Choose e (with e < n) that has no common factors with z. (e, z are 'relatively prime‘ or coprime).
e should also be different than p,q
4. Choose d such that ed-1 is exactly divisible by z.
(in other words: ed mod z = 1 ).
5. Public key is (n,e). Private key is (n,d).
defines the range
In mathematics, a prime number (or a prime) is a natural number
that has exactly two (distinct) natural number divisors, which are 1
and the prime number itself. The first 30 prime numbers are 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, 101, 103, 107, 109, and 113
RSA: Encryption, decryption
0. Given (n,e) and (n,d) as computed above 1. To encrypt bit pattern, m, compute e
c = me mod n (i.e., remainder when m is divided by n) 2. To decrypt received bit pattern, c, compute
m = c mod n (i.e., remainder when c is divided by n)
Magic happens!
m = (memod n)dmod n
RSA: an important property
The following property will be very useful later: K-(K+(m)) = m = + -
K (K (m)) BBB
use public key first, followed by private key
use private key first, followed by public key
result is the same!
Network Security 8-8
Why is RSA secure?
suppose you know Bob’s public key (e,n). How hard is it to determine d?
essentially need to find factors of n without knowing the two factors p and q (p and q are prime numbers)
fact: factoring a big number is hard
RSA:how strong is it??
RSA Challenges:
Prize offered to anyone who can break an RSA key of a certain size
Progress in this challenge should give an insight into which key sizes are still safe and for how long
https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
US$200,000.00 for whoever solves a 2048 bit factorization
problem. No one claimed the prize so far...
Last challenge solved:
RSA-576 $10,000 Factored in 2003 by J. Franke et al.
Using a powerful parallel machine and very clever algorithms
The RSA challenges ended in 2007
Currently RSA-2048 is commonly used in practice
RSA key's size matters, see next...
Bank securely online
Two-Level Authentication
• In order to transact on ANZ Digital Banking, users are required to be authenticated twice. The first level authentication is performed through the use of the Username and Password, while the second level is through One-time Password generated with your Security Device or sent to your mobile number registered with ANZ.
128-bit Secure Socket Layer (SSL) encryption
• The 128-bit Secure Socket Layer (SSL) encryption is an international standard that other Financial Centres in the world uses for securing data communication between the browser and websites. Digital certificate technology is used to ensure transaction privacy, message integrity and server-side authentication. This serves as an assurance that the website runs legitimately under the care of the Bank.
• All data sent to and from ANZ is "scrambled" and "reassembled" between ANZ and your personal computer using 128-bit encryption, the highest
level of encryption commercially available.
Network Security
RSA example:
Bob chooses p=5, q=7. Then n=35, z=24.
e=5 (so e and z are relatively prime).
encrypt: decrypt:
letter m m c=m mod n
d=29 (so ed-1 exactly divisible by z.) ee
l 12 248832
c m = c mod n letter
d17 12l c = 481968572106750915091411825223072000 - too big !! (int type)
There’s an efficient way of solving this! (will be discussed later)
ASCII table (capital letters):
Plain text, and its ASCII equivalent:
After concatenation,
Computing for the cipher text,
Recovering the plain text and testing for equivalence,
RSA: Computing for d
Trial and error approach
Choose p=5, q=7.
Then n=35, z=(5-1)(7-1)=24.
e=? (so e, z relatively prime).
Could not be 3, but could be 5,7,11,13, etc... choose e=5 (a better choice would be e≠p & e≠q...)
d=? For really small numbers, by trial and error: try d=11,13,17...29 until
d=29 (so ed-1 exactly divisible by z).
Network Security
Issues with this simplistic example:
Trial and error approach
e should be different than p,q
Once we choose e, how to find d?
Trial and error will not solve it for large keys!
In practice, use a bigger number, e.g. 300 digits (e=3 is weak) Solution: Use Extended Euclidean Algorithm to find a suitable d
Network Security
How can we check if the e that we picked is a coprime of z?
We can apply the Euclidean algorithm for solving this.
Recall: RSA
Network Security
How can we check if the e that we picked is a coprime of z?
Euclidean Algorithm
• an efficient method for computing the greatest common divisor (gcd) of two numbers
• gcd - the largest number that divides both of them without leaving a remainder.
If e & z are co-primes, then their gcd must be 1.
Network Security
Find the gcd of two numbers, a and b Check if e & z are coprimes.
Euclidean Algorithm gcd(a,b):
Recall: RSA
An example of the Euclid's algorithm:
say, p=11, q=5, and e=7. So, n=55 and z=40 Making sure that e and z are relative primes:
Dividend Divisor Remainder Quotient
407 5 (int)40 / 7
Use z as the dividend, and e as divisor. Calculate their integer quotient.
Network Security
Find the gcd of two numbers, a and b Check if e & z are coprimes. Euclidean Algorithm gcd(a,b):
An example of the Euclid's algorithm:
say, p=11, q=5, and e=7. So, n=55 and z=40 Making sure that e and z are relative primes:
Dividend Divisor Remainder Quotient
40 7 5 5 remainder((int)40 / 7 )
Use z as the dividend, and e as divisor.
Calculate the remainder of the division operation. Network Security
Find the gcd of two numbers, a and b Check if e & z are coprimes.
Euclidean Algorithm gcd(a,b):
Recall: RSA
An example of the Euclid's algorithm:
say, p=11, q=5, and e=7. So, n=55 and z=40 Making sure that e and z are relative primes:
Dividend Divisor Remainder Quotient
40 7 5 5 751
Stop when the remainder turns to 0
Network Security
Find the gcd of two numbers, a and b Check if e & z are coprimes.
Euclidean Algorithm gcd(a,b):
Recall: RSA
An example of the Euclid's algorithm:
say, p=11, q=5, and e=7. So, n=55 and z=40 Making sure that e and z are relative primes:
Dividend Divisor Remainder Quotient
40 7 5 5 7521
Stop when the remainder turns to 0
Network Security
Find the gcd of two numbers, a and b Check if e & z are coprimes.
Euclidean Algorithm gcd(a,b):
Recall: RSA
An example of the Euclid's algorithm:
say, p=11, q=5, and e=7. So, n=55 and z=40 Making sure that e and z are relative primes:
Dividend Divisor Remainder Quotient
40 7 5 5 7521 5212 2102
When the remainder turns to 0, check to see if the divisor is 1
gcd(z,e) = 1
Stop when the remainder turns to 0
Therefore, z and e are coprimes. That also means we picked the right value for e.
Network Security
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com