Breaking RSA (GCD of multiple keys)

Computer Science Level 1

You have looked up several people's public keys, some of which are below. Some of them are vulnerable, because they are divisible by the same prime. What prime is that?

Key #1: 1196311
Key #2: 1250759
Key #3: 1362733
Key #4: 1462991
Key #5: 1509349

983 1217 1361 1439

Alexander Katz by Alexander Katz , 24, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Arulx Z
Jan 13, 2016

Checking for combinations of 2 numbers will be enough 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
import itertools

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

for x in list(itertools.combinations([1196311, 1250759, 1362733, 1462991, 1509349], 2)):
    temp = gcd(x[0], x[1])
    if temp != 1:
        print temp

4 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

This is why the security of these keys is so dependent on the size of the primes.

@Calvin Lin , it true that the size of the security key needs to be large but knowing that 2 large keys share the same prime is bad enough too. For eg, here's the GCD of 2 large semi-primes. The program execution completes within a second. Euclidean algorithm makes it very easy and fast. 

1
2
3
4
5
6
7
8
9
 
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

m = 9091213529597818878440658302600437485892608310328358720428512168960411528640933367824950788367956756806141 * 435958568325940791799951965387214406385470910265220196318705482144524085345275999740244625255428455944579
n = 9091213529597818878440658302600437485892608310328358720428512168960411528640933367824950788367956756806141 * 562545761726884103756277007304447481743876944007510545104946851094548396577479473472146228550799322939273

print gcd(m, n)

Arulx Z - 5 years, 5 months ago

Log in to reply

Right, so the goal for having large primes, is to reduce the likelihood that the primes used are the same.

Calvin Lin Staff - 5 years, 4 months ago
Bhaskar Pandey
May 21, 2021 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
 
# Definitely tougher than Level 1!
num = 1509349*1196311*1250759*1462991*1362733 
lis = [1509349, 1196311,1250759, 1462991,1362733]
def gcd(a,b):
    if min(a,b)<2:
        return 1
    if a%b:
        return gcd(b,a%b)
    return b
for i in lis:
    print(gcd(i,num//i))
# Now the number other than 1 in the output is the desired answer

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...