程序代写案例-CPSC 418/MATH
CPSC 418/MATH 318 Introduction to Cryptography
Public Key Cryptography, RSA, More Number Theory
Renate Scheidler
Department of Mathematics & Statistics
Department of Computer Science
University of Calgary
Week 9
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 1 / 39
Outline
1 Public-Key Cryptography
2 The RSA Cryptosystem
3 More Number Theory – Modular Inverses
4 Efficiency of RSA
5 Security of RSA
Mathematical Security of RSA
Attacks on Certain Scenarios
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 2 / 39
Public-Key Cryptography
Back to Cryptographic Key Agreement
Recall efficient solutions to the key establishment problem:
1 Diffie-Hellman key agreement protocol
2 Public key cryptography — next!
Also used for authentication — later!
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 3 / 39
Public-Key Cryptography
Public-Key Cryptography
Whitfield Diffie and Martin Hellman, “New Directions in Cryptography”,
1976.
Note that Diffie and Hellman did not describe a specific means of
implementing a public-key cryptosystem.
They merely described how one could be used to achieve security,
authentication, (and indirectly, integrity and non-repudiation).
Public key crypto was also secretly discovered in 1970 as “non-secret
encryption” by James H. Ellis of the UK’s Government Communications
Headquarters (GCHQ)
Disclosed in 1987; see
http://cryptocellar.org/cesg/possnse.pdf
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 4 / 39
Public-Key Cryptography
Idea of Public-Key Cryptography
Every user has two keys:
Encryption key is public (so everyone can encrypt messages)
Decryption key is only known to the receiver
Deducing the decryption key from the encryption key should be
computationally infeasible.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 5 / 39
Public-Key Cryptography
Diagram of a Public-Key Cryptosystem
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 6 / 39
Public-Key Cryptography
Trap-door One-Way Functions
Definition 1 (Trap-door one-way function)
A function f that satisfies the following properties:
1 Ease of Computation: f (x) is easy to compute for any x .
2 “Trap-door Pre-image Resistance”: Given y = f (x) it is
computationally infeasible to determine x unless certain special
information used in the design of f is known.
When this trap-door k is known, there exists a function g which is easy
to compute such that x = g(k, y).
Key to designing public-key cryptosystems: decryption key acts as a trap
door for the encryption function.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 7 / 39
Public-Key Cryptography
Public-Key Cryptosystem
Definition 2 (Public Key Cryptosystem (PKC))
A PKC consists of a plaintext space M, a ciphertext space C, a public key
space K, and encryption functions EK1 :M→ C, indexed by public keys
K1 ∈ K, with the following properties:
1 For every public key K1, there exists a private key K2 such that the
encryption function EK1 has a left inverse DK2 , i.e.
DK2(EK1(M)) = M for all M ∈M.
2 EK1(M) and DK2(C ) are easy to compute when K1 and K2 are known.
3 Given K1, EK1 , and C = EK1(M), it is computationally infeasible to
find M or K2.
By properties 1-3, EK1 is a trap-door one-way function with trap door K2.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 8 / 39
Public-Key Cryptography
Schematic of a Public-Key Cryptosystem
K
2
K
1
EAVESDROPPER
MESSAGE
SOURCE
KEY SOURCE
COMMUNICATION CHANNEL
M K1C = E (M) MRECEIVER
WHO DECRYPTS
K2C USING D (C)
TRANSMITTER
ENCRYPTS M
TO E (M)
K1
Note 1
In a public-key cryptosystem (PKC), it is not necessary for the key channel
to be secure.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 9 / 39
Public-Key Cryptography
Properties of a PKC
Unlike conventional cryptosystems, messages encrypted using public key
cryptosystems contain sufficient information to uniquely determine the
plaintext and the key (given enough ciphertext, resources etc)
The entropy contained in these systems is zero.
This is the exact opposite of a perfectly secret system like the
one-time pad.
Security in a public key cryptosystem lies solely in the computational cost
of computing the plaintext and/or private key from the ciphertext
(computional security).
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 10 / 39
Public-Key Cryptography
Hybrid Encryption
All PKCs in use today are much slower (by a factor of 1000-1500 or so)
than conventional systems like AES, so they are generally not used for bulk
encryption. Most common uses:
Encryption and transmission of keys for conventional cryptosystems
(hybrid encryption) – alternative to Diffie-Hellman
Authentication and non-repudiation via digital signatures (later).
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 11 / 39
The RSA Cryptosystem
The RSA Cryptosystem
Named after Ronald Rivest, Adi Shamir and Leonard Adleman, 1978.
Initially, NSA pressured the RSA inventors to keep their invention secret.
Independently invented in 1973 by Clifford Cocks of CESG
(Communications-Electronics Security Group, part of GCHQ) after he
learned about Ellis’ concept of non-secret encryption
Disclosed in 1997; see
http://cryptocellar.org/cesg/notense.pdf
Both encryption and decryption are modular exponentiations (same
modulus, different exponents):
Encryption: C ≡ Me (mod n)
Decryption: M ≡ Cd (mod n)
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 12 / 39
The RSA Cryptosystem
RSA Setup
The designer
1 Selects two distinct large primes p and q (each around 21536 ≈ 10463)
2 Computes n = pq and φ(n) = (p − 1)(q − 1).
3 Selects a random integer e ∈ Z∗φ(n) (so 1 ≤ e < φ(n) and
gcd(e, φ(n)) = 1).
4 Solves the linear congruence
de ≡ 1 (mod φ(n))
for d ∈ Z∗φ(n).
5 Keeps d , p, q secret and makes n and e public:
The public key is K1 = (e, n)
The private key is K2 = {d}
(or (d , p, q); see Problem 2 on Assignment 3).
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 13 / 39
The RSA Cryptosystem
RSA Encryption and Decryption
Encryption: Messages for the designer are integers in Z∗n
E.g. divide a bit string into blocks of bit length ≤ blog2(n)c.
Interpret each block as an integer M with 0 < M < n via its binary
representation.
To send M encrypted, compute and send
C ≡ Me (mod n) where 0 < C < n .
Decryption: To decrypt C , the designer computes
M ≡ Cd (mod n) where 0 < M < n .
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 14 / 39
The RSA Cryptosystem
RSA Toy Example
Choose p = 11 and q = 19.
n = 11 · 19 = 209 and φ(n) = (11− 1)(19− 1) = 10 · 18 = 180.
Chose e = 7 and note that gcd(7, 180) = 1. Then d = 103.
(Verify that 7 · 103 ≡ 1 (mod 180).)
Public key: (7, 209)
Private key: 103
Encryption of M = 176 is 1767 ≡ 187 (mod 209).
Decryption of C = 187 is 187103 ≡ 176 ≡ M (mod 209).
(Use binary exponentiation for encryption and decryption.)
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 15 / 39
The RSA Cryptosystem
Why this Works – Correctness of RSA
Euler’s Theorem
If a, n ∈ Z with n > 0 and gcd(a, n) = 1, then aφ(n) ≡ 1 (mod n).
We have
Cd ≡ (Me)d ≡ Med (mod n),
Since d is chosen such that ed ≡ 1 (mod φ(n)) we have
ed = 1 + kφ(n) for some k ∈ Z,
and hence
Cd ≡ Med ≡ M1+kφ(n) ≡ MMkφ(n) ≡ M(Mφ(n))k (mod n) .
Euler’s Theorem implies that Mφ(n) ≡ 1 (mod n), so we have
Cd ≡ M(Mφ(n))k ≡ M(1)k ≡ M (mod n) .
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 16 / 39
The RSA Cryptosystem
What if gcd(M , n) 6= 1?
We have assumed that gcd(M, n) = 1 in the description of RSA and for
applying Euler’s Theorem. Is this a problem?
Can prove that encryption/decryption still work.
The probability that gcd(M, n) 6= 1 is 1/p + 1/q, i.e., very small.
Note that since n = pq and M < n, gcd(M, n) ∈ {1, p, q}. In the rare
case that this gcd exceeds 1, we will find a factor of n.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 17 / 39
More Number Theory – Modular Inverses
Modular Inverses
In RSA, given φ(n) = (p− 1)(q − 1) and e ∈ Z∗φ(n), the designer must find
d ∈ Z∗Φ(n) such that
ed ≡ 1 (mod φ(n)) .
This is a particular instance of the modular inverse problem: given m ∈ N
and a ∈ Z∗m, solve (efficiently) the congruence
ax ≡ 1 (mod m)
for x .
Note that this congruence is equivalent to the assertion that m divides
ax − 1, i.e. there exists y ∈ Z such that ax − 1 = ym. Equivalently:
Bezout’s Identity: ax −my = 1 = gcd(a,m).
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 18 / 39
More Number Theory – Modular Inverses
Linear Diophantine Equations
Given a, b ∈ Z, not both 0, solve the linear Diophantine equation
ax + by = gcd(a, b) .
Note: we may restrict to the case when a, b > 0:
We have gcd(a, b) = gcd(−a, b) = gcd(a,−b) = gcd(−a,−b).
If a < 0, use −a and solve for (−x , y); similarly for b < 0.
If a = 0 (and b > 0), the equation becomes
by = gcd(b, 0) = b
with solution y = 1 and x can be any integer; similarly for b = 0.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 19 / 39
More Number Theory – Modular Inverses
Euclidean Algorithm
Diophantine equations and the Euclidean algorithm are named after
Diophantus and Euclid, respectively. Both were Greek mathematicians
who lived in Alexandria around 300 BCE.
The Euclidean algorithm finds greatest common divisors via repeated
division with remainder. Given a, b ∈ Z, b > 0, and gcd(a, b) = 1 :
a = q0b + r0 q0 = ba/bc, 0 < r0 < b
b = q1r0 + r1 q1 = bb/r0c, 0 < r1 < r0
r0 = q2r1 + r2 q2 = br0/r1c, 0 < r2 < r1
...
rn−3 = qn−1rn−2 + rn−1 rn−1 = gcd(a, b)
rn−2 = qnrn−1 + rn rn = 0
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 20 / 39
More Number Theory – Modular Inverses
Termination
Notice that the sequence of remainders (the ri ) is non-negative and strictly
decreasing
Thus, the sequence is finite (algorithm terminates).
Theorem 1 (Lame´, 1844)
n < 5 log10 min(a, b).
More exactly, Lame´’s Theorem states
n ≤ logτ (min(a, b) + 1)
where τ = (1 +

5)/2 is the golden ratio.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 21 / 39
More Number Theory – Modular Inverses
Extended Euclidean Algorithm Via Back Substitution
gcd(a, b) = rn−1 = rn−3 − qn−1rn−2 (1)
rn−2 = rn−4 − qn−2rn−3 (2)
rn−3 = rn−5 − qn−3rn−4 (3)
...
...
So gcd(a, b)
(1)
= rn−3 + (−qn−1)rn−2
(2)
= rn−3 + (−qn−1)(rn−4 − qn−2rn−3)
= (−qn−1)rn−4 + (1 + qn−1qn−2)rn−3
(3)
= (−qn−1)rn−4 + (1 + qn−1qn−2)(rn−5 − qn−3rn−4)
= (· · · )rn−5 + (· · · )rn−4
= · · ·
= (· · · )a + (· · · )b
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 22 / 39
More Number Theory – Modular Inverses
Extended Euclidean Algorithm Via Bezout’s Method
Let A−2 = 0, A−1 = 1, B−2 = 1, B−1 = 0 and
Ak = qkAk−1 + Ak−2, Bk = qkBk−1 + Bk−2
for k = 0, 1, . . . .
We have An = a and Bn = b (n from above), and
AkBk−1 − BkAk−1 = (−1)k−1 .
Putting k = n yields
AnBn−1 − BnAn−1 = (−1)n−1
a(−1)n−1Bn−1 + b(−1)nAn−1 = 1 .
Thus, a solution of ax + by = 1 is given by
x = (−1)n−1Bn−1, y = (−1)nAn−1 .
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 23 / 39
More Number Theory – Modular Inverses
Bezout Tableau
Bezout’s method can be represented compactly as a tableau as follows:
q0 q1 q2 · · · qn−1
0 1 A0 A1 A2 · · · An−1
1 0 B0 B1 B2 · · · Bn−1
Each entry in the second and third row is computed by multiplying the
quotient qi in the current column by the previous entry in the same row
and adding it to the entry before that in the same row.
Example 3
Solve 44x + 13y = 1.
44 = 3 · 13 + 5
13 = 2 · 5 + 3
5 = 1 · 3 + 2
3 = 1 · 2 + 1
3 2 1 1
0 1 3 7 10 17
1 0 1 2 3 5
x = (−1)4−1 · 5 = −5
y = (−1)4 · 17 = 17
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 24 / 39
More Number Theory – Modular Inverses
Modular Inverses
Recall that Z∗m = {a ∈ Zm | gcd(a,m) = 1} is the set of integers between
1 and m that are coprime to m.
Z∗m consists of exactly those integers that have modular inverses:
for every a ∈ Z∗m, there exists x ∈ Z∗m such that ax ≡ 1 (mod m).
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 25 / 39
More Number Theory – Modular Inverses
Computing Modular Inverses
Given a ∈ Z∗m, solve the linear congruence ax ≡ 1 (mod m) for x ∈ Z∗m.
We want x such that
m | ax − 1 =⇒ ax − 1 = ym =⇒ ax −my = 1 .
Can be solved using the Extended Euclidean Algorithm.
We only need to compute the Bi because we only need x , not y .
When using Bezout’s method, be sure to start with a = q0m + r0,
even if a < m (so q0 = 0), else you get the wrong count for the
number n of division steps.
Always check your answer!
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 26 / 39
More Number Theory – Modular Inverses
A Back Substitution Example
Solve 95x ≡ 1 (mod 317) for x (mod 317) using back substitution.
Here a = 95 and b = 317. The Euclidean algorithm yields
95 = 317 · 0 + 95
317 = 95 · 3 + 32 (1)
95 = 32 · 2 + 31 (2)
32 = 31 · 1 + 1 (3)
31 = 1 · 31 + 0
Thus, gcd(95, 317) = 1 and back substitution yields
1
(3)
= 32− 31 (2)= 32− (95− 2 · 32) = 3 · 32− 95
(1)
= 3(317− 3 · 95)− 95 = 3 · 317 + (−10) · 95 .
So 1 ≡ (−10) · 95 (mod 317) and hence x ≡ −10 ≡ 307 (mod 317).
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 27 / 39
More Number Theory – Modular Inverses
An Example for Bezout’s Method
Solve 95x ≡ 1 (mod 317) for x (mod 317) using Bezout’s method.
Recall the Euclidean algorithm for a = 95 and b = 317:
95 = 317 · 0 + 95 q0 = 0
317 = 95 · 3 + 32 q1 = 3
95 = 32 · 2 + 31 q2 = 2
32 = 31 · 1 + 1 q3 = 1
31 = 1 · 31 + 0 q4 = 31
So n = 4 and our solution will be x ≡ (−1)4−1B4−1 ≡ −B3 (mod 317).
The Bezout tableau for the quantities Bk is
0 3 2 1
1 0 1 3 7 10
So x ≡ −10 ≡ 307 (mod 317).
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 28 / 39
Efficiency of RSA
Efficiency of RSA
Set-up (need only be done once):
Prime generation uses a pseudo-random number generator (PRNG),
followed by a probable primality test (like the Fermat test).
Generating e again requires a PRNG and one gcd calculation (EA) –
or just pick your favourite e.
Computing n and φ(n) is negligible.
Computing d requires finding a modular inverse (EEA)
Encryption and Decryption: modular exponentiation (like Diffie-Hellman).
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 29 / 39
Security of RSA
Security of RSA
RSA Problem (extracting e-th roots modulo n):
Given e, n and C ∈ Z∗n, find M ∈ Z∗n with Me ≡ C (mod n).
Integer Factorization Problem (IFP):
Given an integer N > 1, find a non-trivial factor of N.
If an adversary can solve an instance of the IFP, she can solve the
RSA problem (by factoring n and finding the private key d in the
same way as the designer).
It is unknown if there are ways of solving the RSA problem without
factoring (or solving one of the other equivalent problem listed below).
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 30 / 39
Security of RSA Mathematical Security of RSA
Total Breaks of RSA
The following approaches break RSA (assume (e, n) is known):
Factoring n, i.e. finding p, q
⇓ φ(n) = (p− 1)(q− 1) ⇑ Solve x2− (n−φ(n) + 1)x + n = 0 for x
Finding φ(n)
⇓ Solve ed ≡ 1 (mod φ(n)) ⇑ See Algorithm 6.10 in Stinson-Paterson
Finding the private key d
Note:
The quadratic equation above has two solutions, namely p and q.
There is an efficient algorithm that given any multiple of φ(n) finds
φ(n) with high probability. Note that ed − 1 is such a multiple.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 31 / 39
Security of RSA Mathematical Security of RSA
Total Breaks of RSA, cont.
All three approaches on the previous slide are computationally equivalent:
if one can be achieved, any of the other two one can be achieved with
very little computational overhead.
so there are three equally good trapdoors here: {p, q}, φ(n) and d .
There is no proof that RSA is secure!
No proof that factoring is hard
Not proved that other methods to solve the RSA problem exist which
do not rely on factoring (i.e. not known whether breaking RSA is
equivalent to factoring n)
In any case, we need to design RSA systems such that n = pq cannot be
factored easily.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 32 / 39
Security of RSA Mathematical Security of RSA
Factoring Record
The fastest known factoring algorithm is again the Number Field Sieve
(slightly different from the DLP NFS, but invented first). Run time:
exp
(
c(log n)1/3(log log n)2/3
)
= nc(log log n/ log n)
2/3
with
c = 3

64/9 = 1.92 . . .
Current RSA modulus factoring record: RSA-250 (250 decimal digits, 831
bits): Boudot-Gaudry-Guillevic-Heninger-Thome´-Zimmerman (February
2020, same people as the DLP record)
21403246502407449612644230728393335630086147151447550177977549208814180234471401366433455190958046796109928518724709145876873
96261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937
= 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
∗ 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
2700 core years with Intel Xeon Gold 6130 CPUs 2.1GHz as reference
See https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 33 / 39
Security of RSA Mathematical Security of RSA
Choice of RSA Parameters
Requirements for p and q:
1 Probable primes with high probability (say 2−100) — use a good
probabilistic primality test.
2 Large: at least 21536 ≈ 10463 (so n is 3072 bits)
3 Not too close together; |p − q| > 2128 for p, q ≈ 21536
4 p and q must be strong primes, i.e. p − 1, q − 1, p + 1, q + 1 all have
a large prime factor (see p. 291 of the Handbook of Applied
Cryptography).
E.g. pick a Sophie Germain prime p′ (so p = 2p′ + 1 is a safe prime)
so that (p + 1)/4 = (p′ + 1)/2 is prime or has a large prime factor;
same for q.
May also want to choose p′ − 1 to have a large prime factor to
avoid cycling attacks (where a modest number of repeated
encryptions “cycle back” to the plaintext)
Choosing random p, q may be sufficient (Rivest-Silverman 1999)
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 34 / 39
Security of RSA Mathematical Security of RSA
Choice of RSA Parameters, cont.
Requirement for e:
For efficiency reasons, e is often chosen small; a popular choice is
e = 216 + 1 = 65537 (great for binary exponentiation, only two ‘1’
bits).
Beware of really small e for certain applications!
In practice, can use e = 3, but only when RSA is used in conjunction
with a secure padding mechanism (eg. OAEP — next week!)
Requirement for d :
d ' n0.25 (Wiener, 1990, see Problem 7 on Assignment 3)
d ' n0.292 (Boneh & Durfee 2000, extension of Wiener’s attack)
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 35 / 39
Security of RSA Attacks on Certain Scenarios
Attack Scenario: Common Modulus, Common Message
Two users with public keys (e1, n) and (e2, n) where gcd(e1, e2) = 1.
Alice sends both users the same message M, encrypted:
Ci ≡ Mei (mod n) , (i = 1, 2) .
The following attack finds M:
1 Use the Extended Euclidean Algorithm to obtain integers x , y with
xe1 + ye2 = 1 .
2 Then
C x1 C
y
2 ≡ (Me1)x(Me2)y ≡ Me1x+e2y ≡ M1 ≡ M (mod n) .
Attack can be extended to more than two users sharing the same modulus.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 36 / 39
Security of RSA Attacks on Certain Scenarios
Attack Scenario: e = 3, Common Message
Three users with public keys (3, n1), (3, n2), (3, n3), gcd(n1, n2, n3) = 1.
(Note that if gcd(ni , nj) > 1, then ni and nj are factored!)
Alice sends all three users the same message M, encrypted:
Ci ≡ M3 (mod ni ) , (i = 1, 2, 3) .
The following attack finds M:
1 Use the Extended Euclidean Algorithm to obtain integers u, v with
1 = un1 + vn2 .
Then n3 = un1n3 + vn2n3.
2 Use the Extended Euclidean Algorithm to obtain integers x , t with
1 = xn1n2 + tn3 = xn1n2 + (tu)n1n3 + (tv)n2n3 .
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 37 / 39
Security of RSA Attacks on Certain Scenarios
Attack Scenario: e = 3, Common Message, cont’d
3 Put
C ≡ C3xn1n2 + C2(tu)n1n3 + C1(tv)n2n3 (mod n1n2n2) .
Then
C ≡ Ci ≡ M3 (mod ni ) (i = 1, 2, 3) .
4 Now we have
0 < C < n1n2n3
0 < M3 < n1n2n3
C ≡ M3 (mod n1n2n3)
This implies that C = M3 and hence M = 3

C .
Attack can be extended to any e and at least e users.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 38 / 39
Security of RSA Attacks on Certain Scenarios
Attack Scenario: e = 3, Three Similar Messages
Suppose a user has RSA public key (3, n).
Alice sends three messages that differ in a few places in a known way to
that user. Then these messages can be efficiently found by an adversary
using linear algebra modulo n.
Attack can be extended to any e and at least e similar messages with
known differences.
Renate Scheidler (University of Calgary) CPSC 418/MATH 318 Week 9 39 / 39

欢迎咨询51作业君
51作业君 51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: ITCSdaixie