Understanding Common Factor Attacks

This is a write up for the programming element of Understanding Common Factor Attacks: An RSA Cracking Puzzle. The intro and explanation of the problem can be found here.

Below is the following program I wrote to find the weak key pairs and then decrypt them.

~ Code ~

# For use: Specify fileLocation in Main()

require 'openssl'
require 'rational'
require 'net/http'
require 'uri'

def decrypt(index, p, q, file)
    loc = file

# Getting the new private key in openssl format
    uri = URI('http://rose.makesad.us/~schoen/cgi-bin/private-from-pq.cgi?%s&%s'% [p,q])
    x = Net::HTTP.get(uri)
    privateKey = x[135..(x.length)]

# Write private key data to a .pem file
    file = File.new("%s.pem" % [index], "w")
    file.write(privateKey)
    file.close

# Decrypt
    key = OpenSSL::PKey::RSA.new File.read '%s.pem' %[index]
    plainText = key.private_decrypt File.read '%s/%s.bin' % [loc, index]
    puts "\nDecrypted Message[%s]:\n%s" % [index, plainText]

# Delete .pem files
    File.delete("%s.pem"%[index])

end

def main()

    c = 1

    fileLocation = '/path/to/file/locatation/challenge'

    for z in 1..100 do
        a = '%s/%s.pem' % [fileLocation, z]
        key1 = (OpenSSL::PKey::RSA.new File.read a).n
        for i in 1..100 do
            b = '%s/%s.pem' % [fileLocation, i]
            key2 = (OpenSSL::PKey::RSA.new File.read b).n
            q = key1.gcd(key2)
            if q > 1 and i!=z and z<i
                # Find p Values
                p1 = key1.to_i/(q.to_i)
                p2 = key2.to_i/(q.to_i)
                puts "\n~~~~~~~~~~ Pair %s ~~~~~~~~~~" % [c]
                puts "(q) GCD:\n%s\n\n" % [q]
# Key 1 use z index
                puts "(n) Public Key for Message[%s]:\n%s" % [z, key1]
                puts "(p) :\n%s" % [p1]
                decrypt(z, p1, q, fileLocation)
# Key 2 use i index
                puts "\n(n) Public Key For Message [%s]:\n%s" % [i, key2]
                puts "(p) :\n%s" % [p2]
                decrypt(i, p2, q, fileLocation)

                c += 1
            end
        end
    end
end

main()
Advertisements