Computing the Square Roots of Unity to break RSA using Quantum Algorithms

Computing the Square Roots of Unity to
break RSA using Quantum Algo
Dr. Dharma Ganesan, Ph.D.,

Disclaimer
● The opinions expressed here are my own
○ But not the views of my employer
● The source code fragments and exploits shown here can be reused
○ But without any warranty nor accept any responsibility for failures
● Do not apply the exploit discussed here on other systems
○ Without obtaining authorization from owners
2

Goal
● Break RSA using Peter Shor’s quantum algorithm
○ But, we will not look into Quantum Computing
○ We will find the square roots of unity on a classical computer
● Investigate the square root of unity (i.e., sqrt(1)) in a Finite Group
○ Algorithm 1: Naïve/Bruteforce
○ Algorithm 2: Random Search
○ Algorithm 3: Peter Shor’s period calculation algorithm
○ Algorithm 4: Our little tweaks of Peter Shor’s period function (bounded search)
3

Prerequisite
Some familiarity with the following topics will help to follow the rest of the slides
● Group Theory
● Number Theory
● Algorithms and Complexity Theory
● If not, it should still be possible to obtain a high-level overview
4

Agenda
● Mathematical foundation/facts
● Brief overview of RSA
● Different algorithms to find the square roots of unity (in a finite group)
● Demos of finding the square roots of unity to factor composite numbers
● Conclusion
5

6
Notations and Facts
GCD(x, y): The greatest common divisor that divides integers x and y
Co-prime: If gcd(x, y) = 1, then x and y are co-primes
Zn
= { 0, 1, 2, …, n-1 }, n > 0; we may imagine Zn
as a circular wall clock
Z*
n
= { x ∈ Zn
| gcd(x, n) = 1 }; (additional info: Z*
n
is a multiplicative group)
φ(n): Euler’s Totient function denotes the number of elements in Z*
n
φ(nm) = φ(n).φ(m) (This property is called multiplicative)
φ(p) = p-1, if p is a prime number

Notations and Facts ...
● x ≡ y (mod n) denotes that n divides x-y; x is congruent to y mod n
● Euler’s Theorem: aφ(n)
≡ 1 (mod n), if gcd(a, n) = 1
● Fermat’s Little Theorem: ap
≡ a (mod p)
● Gauss’s Fundamental Theorem of Arithmetic: Any integer greater than 1 is
either a prime or can be written as a unique product of primes
○ Euclid’s work is the foundation for this theorem, see The Elements
● Euclid’s Lemma: if a prime p divides the product of two natural numbers a
and b, then p divides a or p divides b
● Euclid’s Infinitude of Primes (c. 300 BC): There are infinitely many primes
7

How can Bob send a message to Alice securely?
8
Public Key PuA
● Alice and Bob never met each other
● Bob will encrypt using Alice’s public key
○ Assume that public keys are known to the world
● Alice will decrypt using her private key
○ Private keys are secrets (never sent out)
● Bob can sign messages using his private key
○ Alice verifies message integrity using Bob’s public key
● Note: Alice and Bob need other evidence (e.g., passwords,
certificates) to prove their identity to each other
● Who are Alice, Bob, and Eve?
Private Key PrA
Public Key PuB
Private Key PrB

RSA Public Key Cryptography System
● Published in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman
● Rooted in elegant mathematics - Group Theory and Number Theory
● Core idea: Anyone can encrypt a message using recipient's public key but
○ (as far as we know) no one can efficiently decrypt unless they got the matching private key
● Encryption and Decryption are inverse operations (math details later)
○ Work of Euclid, Euler, and Fermat provide the mathematical foundation of RSA
● Eavesdropper Eve cannot easily derive the secret (math details later)
○ Unless she solves “hard” number theory problems that are computationally intractable
9

RSA - Key Generation Algo
1. Select an appropriate bitlength of the RSA modulus n (e.g., 2048 bits)
○ Value of the parameter n is not chosen until step 3; small n is dangerous (details later)
2. Pick two independent, large random primes, p and q, of half of n’s bitlength
○ In practice, q < p < 2q to avoid attacks (e.g., Fermat’s factorization)
3. Compute n = p.q (n is also called the RSA modulus)
4. Compute Euler’s Totient (phi) Function φ(n) = φ(p.q) = φ(p)φ(q) = (p-1)(q-1)
5. Select numbers e and d from Zn
such that e.d ≡ 1(mod φ(n))
○ e must be relatively prime to φ(n) otherwise d cannot exist (i.e., we cannot decrypt)
○ d is the multiplicative inverse of e in Zn
6. Public key is the pair <n, e> and private key is 4-tuple <φ(n), d, p, q>
10

RSA Trapdoor
● RSA: Zn
→ Zn
● Let x and y ∈ Zn
● y = RSA(x) = xe
mod n
○ We may view x as a plaintext, and y as the corresponding ciphertext
● x = RSA-1
(y) = yd
mod n
● e and d are also called encryption and decryption exponents, respectively
● In practice, some random padding is used (not relevant for this presentation)
11

RSA Trapdoor variables’ dependency graph
12
Private variable
Public variable
Note: If we can factor n and find p and q, then private keys are open to the world

What are the square roots of unity in Z?
● 1 and -1 are the two square roots of one because (±1)2
= 1
● This is true only if we work in the infinite set of integers Z
● In Cryptography, we often work with finite groups
● There are other non-trivial roots of unity other than ±1 in Z*
n
13

Square roots of unity in a finite group Z*
n
Consider this tiny multiplicative group Z*15
= {1, 2, 4, 7, 8, 11, 13, 14}
The square roots of unity are 1, 4, 11, and 14
Note that 14 ≡ -1 mod 15 (basically -1 is the same as 14)
But, we have two other roots 4 and 11 of unity (e.g., 4*4 = 1 mod 15)
1 and 14 are trivial roots of unity, whereas 4 and 11 are non-trivial roots of unity
Fact: Let n = pq, where p and q are odd primes, then there are four roots of unity
14

Algorithm: Factor n using the square roots of unity
Problem: Given a composite number n and sqrt(1), find the factors p and q of n
Let x be a square root of 1, then x2
= 1 (mod n)
Thus, x2
- 1 = 0 (mod n) ⇒ (x+1)(x-1) = 0 (mod n)
This means that n divides (x+1)(x-1)
If (x+1) and (x-1) are not multiples of n, then the factors of n are the following:
p = gcd(x+1, n) or gcd(x-1, n); q = n/p
15

Toy example: Let’s factor n = 15 using Z*15
Z*15
= {1, 2, 4, 7, 8, 11, 13, 14}
Since 4 and 11 are square roots of unity, we can use one of them to factor n
Let x = 4
x2
= 1 (mod 15)
(x+1)(x-1) = 0 (mod 15)
Factor p = gcd(x+1, 15) = gcd(5, 15) = 5; Factor q = n/p = 15/5 = 3
16

Factoring n using the square roots of unity ...
If we can find the non-trivial square roots on n, then we can factor n
Let’s investigate how easy it is to find the sqrt(1) in a finite multiplicative group
Four different algorithms to find the sqrt(1):
1. Bruteforce/Naive
2. Random Search
3. Peter Shor’s Quantum Algorithm
4. Our little tweaks of Shor’s algorithm
17

Algorithm 1: Naïve sqrt(1) in Zn
*
Step 1: x = 0
Step 2: if(x < n) goto step 3; otherwise goto step 5
Step 3: if(x2
= 1 mod n) then x is a square root of one.
Step 4: x = x + 1. goto step 2.
Step 5: End.
18

19
~/crypto/RSA$ java SqrtOneNaive 2086784737
Input bit length = 31
Sqrt(n) = 45681
sqrt(1) = 1 bit length = 1
sqrt(1) = 530886943 bit length = 29
sqrt(1) = 1555897794 bit length = 31
sqrt(1) = 2086784736 bit length = 31
Note: sqrt(n) is only 45681, but sqrt(1) can be the same bit length as n
(See the Appendix for the source code of Sqrt(1) naïve method)
Algorithm 1: Find the sqrt(1) in the group Z*2086784737

Algorithm 1: Analysis of the naïve algorithm
● The naïve algorithm is simple to understand and implement
● However, it is very slow because we enumerate all numbers of the group Zn
● If n is a 2048-bit composite number, this algorithm will perform 22048
iterations
● In other words, it will take several billion years to calculate sqrt(1)
20

Algorithm 2: Random search to find sqrt(1) in Zn
*
Step 1: Pick a random x from Zn
Step 2: if(x = ± 1 mod n) then goto step 1
Step 3: if(x2
= 1 mod n) then x is a sqrt(1) goto step 4; else step 1
Step 4: End.
21

22
dharmalingam_ganesan11@instance-1:~/crypto/RSA$ java RandomSqrtOne 45649
sqrt(1) = 43738
Number of random tries = 236
ddharmalingam_ganesan11@instance-1:~/crypto/RSA$ java RandomSqrtOne 45649
sqrt(1) = 43738
dharmalingam_ganesan11@instance-1:~/crypto/RSA$ java RandomSqrtOne 45649
sqrt(1) = 43738
Algorithm 2: Find the sqrt(1) in the group Z*45649

23
Algorithm 2: Analysis of Random Search Algo
● The random algorithm can find the square roots of one (for “small” n)
● But, it just needs a lots of tries to find a needle in the haystack
● In general, the number of tries is the size of the input composite number
● Random search is not able to find sqrt(1) for very large input n

25
Algorithm 3: Peter Shor’s Algorithm (core idea)
● To find an x such that x2
= 1 (mod n), we compute f(x) = ax
mod n, random a
● Fact: Every element of a finite group generates a cyclic subgroup
● In other words, the function f(x) is the same as the cyclic subgroup <a>
● Thus, f(r) = 1 mod n for some r; equivalently, ar
= 1 mod n for some r
● Once we find such an r, (ar/2
)2
= 1 mod n; (if r is even, the hacker is lucky)
● Thus, ar/2
is the sqrt(1); we know how to factor n once the sqrt(1) is exposed!

Algorithm 3: Finding the period r of the function f(x)
26
x f(x) = ax
mod n
0 a0
mod n
1 a1
mod n
2 a2
mod n
r ar
mod n = 1
● Peter Shor uses quantum computing
to find the period r of the function f(x)
● We implemented this function on my
classical computer (my laptop)
● Just to better understand the inner
beauty of this algorithm

27
~/crypto/RSA$ java -ea SqrtOneShor 45649
period = 1330
sqrt(1) = 1911
period = 4522
sqrt(1) = 43738
period = 22610
sqrt(1) = 1911
period = 22610
sqrt(1) = 1911
period = 4522
sqrt(1) = 1911
period = 22610
sqrt(1) = 43738

28
~/crypto/RSA$ time java -ea SqrtOneShor 1421727721
period = 236941974
Sqrt(1) = 521638680
real 0m47.429s
user 0m47.100s
sys 0m0.288s Period is very large

29
~/crypto/RSA$ java FactorShor 45649
period = 22610
p = 191
q = 239
period = 170
p = 239
q = 191
period = 3230
p = 239
q = 191
Algorithm 3: Factor a small number n = 45649

30
Algorithm 3: Analysis of the period of f(x) = ax
mod n
● The above set of runs shows that the period of f(x) can be very large
○ Thus, we cannot apply this algorithm to find sqrt(1) for a large group Zn
used in RSA
● Remember, we are running the algorithm on a classical computer
● It is good to play with this algorithm on a classical computer to understand it
● Algorithm 4 talks about some little tweaks of Algorithm 3

Algorithm 4: Let’s tweak Peter Shor’s algorithm
What if we put a bound b on the period r?
Step 1: Initialize bound b (e.g., b = n1/2
, n1/4
, etc.), r = 0, success = false
Step 2: Pick a random a from Zn
*
Step 3: if 0 ≤ r ≤ b goto step 4; otherwise goto step 7
Step 4: Compute f(r) = ar
mod n
Step 5: If f(r) != 1 then r = r+1 and goto step 3
Step 6: If r is even, then success = true; otherwise goto step 2
Step 7: If success = true, we found the period r; otherwise goto step 2
31

32
period = 33738
sqrt(1) = 521638680
real 0m45.786s
user 0m45.510s
sys 0m0.244s
Algorithm 4: bound = n1/2

33
period = 18
Square root of one = 521638680
real 6m14.713s
user 6m12.706s
sys 0m1.759s

34
period = 18
real 2m29.435s
user 2m28.400s
sys 0m0.936s

35
period = 6
real 2m31.106s
user 2m29.703s
sys 0m1.304s
Amazing, we found a cyclic subgroup of order 6

Algorithm 4: Analysis of our tweaks
● Z*
n
has even number of elements; there must be cyclic subgroups for each
divisor of |Zn
*|. (This is a theorem in Group Theory)
● The open question is how easy it is to find small cyclic subgroups of Z*n
● If we quickly find one cyclic subgroup, then sqrt(1) are easily revealed
● If we put a bound b on the period r, then sqrt(1) runs quick for a small n
● Our bounded random search variant of Shor’s algorithm is slow for a large n
36

Conclusion
● We studied the problem of finding the square roots of unity in a finite group
● We tried to factor composite numbers using sqrt(1)
● Experimental results showed that finding sqrt(1) in Z*n
where n = pq is “hard”
● We implemented Shor’s function f(x) = ax
mod n on a classical computer
● We learned that in general the period of f(x) is the same size as n
● We made minor tweaks by defining a bound on the period of f(x) = ax
mod n
● More experimentation of our tweaks is part of future work
37

39
import java.math.BigInteger;
import java.security.SecureRandom;
public class SqrtOneNaive implements IBigIntConstants
{
public static void main(String[] args)
{
/* Error handling is omitted */
BigInteger n = new BigInteger(args[0]);
BigInteger x = zero;
while(x.compareTo(n) <= 0) {
// is square(x) = 1 (mod n)?
if(x.multiply(x).mod(n).equals(one)) {
System.out.println(x + " is the square root of one ");
}
x = x.add(one);
}
}
}
Implementation of naïve Sqrt(1) algorithm

40
public static void main(String[] args)
{
BigInteger n = new BigInteger(args[0]); // Error handling code is removed
BigInteger x;
while(true) {
// Pick a random element from Zn
x = BigIntUtil.getRandomElt(n, new SecureRandom());
// We don't want non-trivial roots '1' or '-1'.
// If x = -1 (mod n) or x = 1 (mod n), then we have to restart.
if(x.add(one).mod(n).equals(zero) ||
x.subtract(one).mod(n).equals(zero)) { continue; }
if(x.multiply(x).mod(n).equals(one)) {
System.out.println(x + " is the square root of one ");
System.out.println("Number of random tries = " + counter);
break;
}
}
}
Implementation of random Sqrt(1) algorithm

41
Finding the Sqrt(1) using Peter Shor’s
algorithm (simplied)

References
● W. Diffie and M. E. Hellman, “New Directions in Cryptography,” IEEE
Transactions on Information Theory, vol. IT-22, no. 6, November, 1976
● R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital
signatures and public-key cryptosystems,” CACM 21, 2, February, 1978
● A. Menezes, P. van Oorschot, and S. Vanstone, “Handbook of Applied
Cryptography,” CRC Press, 1996
● P. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete
Logarithms on a Quantum Computer,” SIAM J.Sci.Statist.Comput. 26 (1997).
42

Computing the Square Roots of Unity to break RSA using Quantum Algorithms

Recommended

More Related Content

What's hot (7)

Similar to Computing the Square Roots of Unity to break RSA using Quantum Algorithms (20)

More from Dharmalingam Ganesan (17)

Recently uploaded (20)

Computing the Square Roots of Unity to break RSA using Quantum Algorithms