(Review) RSA: Choosing keys
Copyright By PowCoder代写 加微信 powcoder
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 (e, n). Private key is (d, n).
defines the range
(Review) RSA: Choosing keys
Choosing a value for e
• Public key is (e, n).
• Private key is (d, n).
• e should be less than n
• eshouldnotbeequaltoporq
• e should be co-prime with z
• In practice, we prefer a big value for e.
(Review) RSA: Choosing keys
Choosing a value for e
• Public key is (e, n).
• Private key is (d, n).
• e should be less than n
• eshouldnotbeequaltoporq
• e should be co-prime with z
• In practice, we prefer a big value for e.
We can pick an arbitrary value for e, then use the Euclidean Algorithm to test if that value is a co-prime with z; that is, if gcd(e,z) is equal to 1. If not, we pick another value for e (e.g. by incrementing the previous e by one, then test that new value. Repeat until successful.
Requirement:
(ed-1) must be exactly divisible by z
(ed-1) modz=0 Rewriting and simplifying,
How to calculate for d such that ed mod z = 1?
We can apply Bézout's identity in solving this. Network Security
Solving for d
Detailed analysis
There exist two integers x,y that satisfy:
ax + by = gcd(a,b)
where a,b are also integers, and
gcd(a,b) is their greatest common divisor This is called the Bézout's identity.
Network Security
Solving for d
Detailed analysis
There exist two integers x,y that satisfy:
ax + by = gcd(a,b)
where a,b are also integers, and
gcd(a,b) is their greatest common divisor
This is called the Bézout's identity.
Now we can solve for d
If we think a,b are z,e then we know that:
• gcd(z,e) = 1 (they are relatively primes)
zx + ey = gcd(z,e)=1 zx + ed = gcd(z,e)=1
How does this equation relate to ed mod z = 1?
Network Security
Is it ok to write this?
Solving for d
Detailed analysis
zx + ed = gcd(z,e)=1
Is it ok to write this?
zx + ed = 1 Expanding the equation,
(zx + ed) mod z = 1 mod z
Network Security
Solving for d
Detailed analysis
zx + ed = gcd(z,e)=1 zx + ed = 1
Is it ok to write this?
(zx + ed) mod z = 1 mod z Expanding further,
zx mod z=?
(zx mod z) + (ed mod z) = 1 0 + ed mod z = 1
5x mod 5 = ?
5 mod 5 = 0
10 mod 5 = 0
Therefore,
zx mod z = 0
Network Security
Solving for d
Detailed analysis
zx + ed = gcd(z,e)=1
Is it ok to write this?
zx + ed = 1
(zx + ed) mod z = 1 mod z (zx mod z) + (ed mod z) = 1
0 + ed mod z = 1 ed modz=1 ed mod z = 1
We can use Bézout's identity to relate x and d to the gcd(z,e)
zx + ed = gcd(z,e)=1 is equivalent to ed mod z = 1 Network Security
For the next step, we can use the Extended Euclidean Algorithm to compute for the coefficients of Bézout's identity.
Given a and b, find x and y that satisfies the equation: ax + by = gcd(a,b)
where a = z, and b = e. zx + ed = gcd(z,e)=1
Solving for y is the same as solving for d.
We can use the Extended Euclidean Algorithm in solving this.
Network Security
Long method
(for completeness of discussion we would like to see the details of this long method, but we will see an automated technique later on)
Long method ax + by = gcd(a,b)
Extended Euclidean Algorithm:
Initial values
(int) remainder quotient
An example with z=40 and e=7 again: gcd
zx + ed ax + by
Calculation Steps:
1. Placezattheremaindercolumn.Calculateforxandy.
2. Move to next row, Place e at the remainder column. Calculate for x and y. 3. Movetonextrow,calculatefortheintegerquotient(z/e)andremainderof
(z/e). Calculate for x and y.
4. Repeat step 3, until remainder is 1.
Long method ax + by = gcd(a,b)
Extended Euclidean Algorithm:
Initial values
(int) quotient
40=40*1+7*0 7=40*0+7*1
Calculation Steps:
An example with z=40 and e=7 again:
gcd(z,e) = zx + ed ax + by
1. Placezattheremaindercolumn.Calculateforxandy.
2. Move to next row, Place e at the remainder column. Calculate for x and y. 3. Movetonextrow,calculatefortheintegerquotient(z/e)andremainderof
(z/e). Calculate for x and y.
4. Repeat step 3, until remainder is 1.
Long method ax + by = gcd(a,b)
Extended Euclidean Algorithm:
Initial values
(int) quotient
40=40*1+7*0 7=40*0+7*1
An example with z=40 and e=7 again:
zx + ed ax + by
Calculation Steps:
1. Placezattheremaindercolumn.Calculateforxandy.
2. Move to next row, Place e at the remainder column. Calculate for x and y. 3. Movetonextrow,calculatefortheintegerquotient(z/e)andremainderof
(z/e). Calculate for x and y.
4. Repeat step 3, until remainder is 1.
Network Security
Long method ax + by = gcd(a,b)
Extended Euclidean Algorithm:
Initial values
(int) quotient
40=40*1+7*0 7=40*0+7*1
5=40*1+7*(-5)
An example with z=40 and e=7 again:
zx + ed ax + by
Calculation Steps:
1. Placezattheremaindercolumn.Calculateforxandy.
2. Move to next row, Place e at the remainder column. Calculate for x and y. 3. Movetonextrow,calculatefortheintegerquotient(z/e)andremainderof
(z/e). Calculate for x and y.
4. Repeat step 3, until remainder is 1.
Network Security
Long method ax + by = gcd(a,b) Extended Euclidean Algorithm:
step (int) quotient
40=40*1+7*0 7=40*0+7*1 5=40*1+7*(-5)
2=40*(-1)+7*6
An example with z=40 and e=7 again:
zx + ed ax + by
Calculation Steps:
1. Place z at the remainder column. Calculate for x and y.
2. Move to next row, Place e at the remainder column. Calculate for x and y.
3. Move to next row, calculate for the integer quotient (z/e) and remainder of (z/e).
Calculate for x and y.
4. Repeat step 3, until remainder is 1.
Network Security
Long method ax + by = gcd(a,b) Extended Euclidean Algorithm:
(int) remainder quotient
40=40*1+7*0 7=40*0+7*1 5=40*1+7*(-5)
2=40*(-1)+7*6
An example with z=40 and e=7 again: gcd
zx + ed ax + by
stop at this row! Problem: we found that d=-17
gcd(40,7) = 1
1=40*3+7*(-17) But we want a positive value for d. To fix this issue, we simply add the value
of z to y, and we subtract e from x. Network Security 22
Long method ax + by = gcd(a,b) Extended Euclidean Algorithm:
(int) remainder quotient
40=40*1+7*0 7=40*0+7*1 5=40*1+7*(-5)
2=40*(-1)+7*6
An example with z=40 and e=7 again: gcd
zx + ed ax + by
stop at this row! Subtract e from x, and add the value of z to y, and we
1=40*3+7*(-17)
To check: 40*(3-7)+7*(-17+40)=40*(-4)+7*(23) = 1
So d=23 is what we will use.
Network Security 23
gcd(40,7) = 1
Automated method
• This algorithm will only work if z and e are relative primes (co-primes).
For automated computation of d
ax + by = gcd(a,b) zx + ed = gcd(z,e)
Extended Euclidean Algorithm:
Using a table with z=40 and e=7: d
step x y w k
gcd quotient
Network Security
For automated computation of d
ax + by = gcd(a,b) zx + ed = gcd(z,e)
Extended Euclidean Algorithm:
Using a table with z=40 and e=7: d
step x y w k
1 1 0 40*1+7*0=40 40 2 0 1 40*0+7*1=7 7
zx + ed = gcd(z,e) .........
INITIALISATION:
Initial values
Based on our study of the long method, we can immediately set the first two rows as follows:
First row: put the value of z in the gcd column. Set x=1, y=0.
Second row: put the value of e in the gcd column. Set x=0, y=1.
gcd quotient
Network Security
For automated computation of d
ax + by = gcd(a,b) zx + ed = gcd(z,e)
Extended Euclidean Algorithm:
Using a table with z=40 and e=7: d
step x y w k
1 1 0 40 2017
STEPS (in a loop) 1. ki=(int)wi-1/wi
Initial values
2. xi = xi-2 - ki-1 xi-1 3. yi = yi-2 - ki-1 yi-1
Loop termination:
• Stop when w (gcd) is equal to 1
4. w = w - k w i i-2 i-1
This algorithm will only work if z and e are relative primes (co-primes). 27
gcd quotient
Network Security
Extended Euclidean Algorithm:
Using a table with z=40 and e=7: d
ax + by = gcd(a,b)
step x y w k
1 1 0 40 20175
1. ki=(int)wi-1/wi
(int) 40/7 = 5
2. xi=xi-2-ki-1xi-1 3. yi=yi-2-ki-1yi-1 4. wi=wi-2-ki-1wi-1
Network Security
(int)quotient
Solve for Step 1.
Extended Euclidean Algorithm:
Using a table with z=40 and e=7: d
ax + by = gcd(a,b)
step x y w k
1 1 0 40 20175
3 1 -5 5 1
1. ki=(int)wi-1/wi
2. xi = xi-2 - ki-1 xi-1
1 – (5*0) = 1
3. yi=yi-2-ki-1yi-1 4. wi=wi-2-ki-1wi-1
Network Security
(int)quotient
Extended Euclidean Algorithm:
Using a table with z=40 and e=7: d
ax + by = gcd(a,b)
step x y w k
1 1 0 40 20175
3 1 -5 5 1
1. ki=(int)wi-1/wi
2. xi=xi-2-ki-1xi-1
3. yi=yi-2-ki-1yi-1
0 – (5*1) = -5
4. wi=wi-2-ki-1wi-1
Network Security
(int)quotient
Extended Euclidean Algorithm:
Using a table with z=40 and e=7: d
ax + by = gcd(a,b)
step x y w k
1 1 0 40 20175
3 1 -5 5 1
1. ki=(int)wi-1/wi
2. xi = xi-2 - ki-1 xi-1 3. yi=yi-2-ki-1yi-1 4. wi = wi-2 - ki-1 wi-1
• Stop when w (gcd) is equal to 1
(int)quotient
40 – (5*7) = 5
Network Security
Extended Euclidean Algorithm:
1. ki=(int)wi-1/wi
Using a table with z=40 and e=7: d
2. xi = xi-2 - ki-1 xi-1 3. yi = yi-2 - ki-1 yi-1 4. wi = wi-2 - ki-1 wi-1
step x y w k
20175 3 1 -5 5 1 4 -1 6 2 2 5 3 -17 1
stop at this row!
• Stop when w (gcd) is equal to 1
If d is negative, d=d+z will be suitable d=-17+40=23
d=23. Done!
Network Security
(int)quotient
gcd(40,7) = 1
Network Security
Extended Euclidean Algorithm:
1. ki=(int)wi-1/wi
Given: p=11, q=3, z=20 and e=3, find d.
2. xi = xi-2 - ki-1 xi-1
3. yi = yi-2 - ki-1 yi-1
4. wi = wi-2 - ki-1 wi-1
1 1 0 20 2013 3
(int)quotient
step x y w k
d = ? Network Security 34
Summary of Techniques
ToCheckife&zarecoprimes. EuclideanAlgorithm gcd(e,z):
Solve for d
zx + ed = gcd(z,e)=1
Extended Euclidean Algorithm
Bézout's identity.
this algorithm will only work if z and e are relative primes (co‐primes).
Network Security
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).
defines the range
e should also be different than p,q
To Check if e & z are coprimes. Euclidean Algorithm gcd(e,z):
4. Choose d such that ed-1 is exactly divisible by z. (in other words: ed mod z = 1 ).
Solve for d Extended Euclidean Algorithm 5. Public key is (e, n). Private key is (d, n).
Network Security
Back to the previous RSA example:
letter m m c=m mod n
c m = c mod n letter
For p=5, q=7. Then n=35, z=24. e=5 (so e, z relatively prime).
d=29 (so ed-1 exactly divisible by z). ee
l 12 248832
cd = 481968572106750915091411825223071697 - too big, overflow !! (int type)
Network Security
Prerequisite: modular arithmetic
x mod n = remainder of (x divided by 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 = (a*b) mod n
Therefore
(amodn)d modn=ad modn
Network Security 8-39
Calculating powers rapidly
Solve 1143 mod 13 = ?
Break it into powers that are multiples of 2.
Sum of powers of 2:
=20 +21+23 +25
43 = 1 + 2 + 8 +32 1143 =11*112 *118 *1132
Calculation of sequence: 11 * 112 * 118 * 1132 (mod 13) =[(11mod13)*(112 mod13)*(118 mod13)*(1132 mod13)]mod13
112 mod 13 = 4 (mod 13) 112 mod 13=4 mod 13=4 114 mod 13 = (112)2 mod 13 = 42 (mod 13)=3 (mod 13)
We do not need to multiply numbers bigger than 13
118 mod 13 = (114)2 mod 13 = 32 (mod 13)=9 (mod 13) 1116 mod 13 = (118)2 mod 13 = 92 (mod 13)=3 (mod 13) 1132 mod 13 = (1116)2 mod 13 = 32 (mod 13)=9 (mod 13)
Putting this together, remember, 1143 = 11 * 112 * 118 * 1132
1143 (mod13)=11*4 *9 *9 (mod13)
Ref: http://web.math.princeton.edu/math_alive/Crypto/Lab2/FastPower.html
Network Security
= 44 *81 (mod13) = 5 *3 (mod13)
= 2 (mod13)
Even better solution:
Repeated Squaring: calculate y = x e mod n int repeatsquare( int x, int e, int n) {
y=1;//initialize y to 1, very important while(e> 0){
This is the key to be used
if (( e % 2 ) == 0) {// e is an even number x = (x*x) % n;
e = e/2; }
c = me mod n m = cd mod n
else { // e is an odd number y = (x*y) % n;
e = e-1; }
return y; //the result is stored in y }
Network Security
Even better solution:
Repeated Squaring: calculate y = x e mod n int repeatsquare( int x, int e, int n) {
y=1;//initialize y to 1, very important while(e> 0){
if (( e % 2 ) == 0) {// e is an even number x = (x*x) % n;
e = e/2; }
else { // e is an odd number y = (x*y) % n;
y=xe modn calculate y = 243 mod 33
e = e-1; }
return y; //the result is stored in y }
x=24, e=3, n=33
242 %33=15
(24*1)%33=24 24 (15*24)%33=30
Network Security
Unconcealed
http://www.di-mgt.com.au/rsa_alg.html
c=me mod n
Avoid the following values of m, as they cannot be concealed by the algorithm:
m = 0, 1 and n-1 will always give the same cipher value no matter how large n is.
The secure properties of RSA encryption only work if me > n
Network Security
DES vs. RSA (Speed of Computation) The exponentiation required by RSA is a very
time-consuming operation.
DES is at least 100 times faster than RSA in software and between 1,000 and 10,000 times faster in hardware.
In practice, Triple DES or AES is used by banking systems, etc.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com