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作业君