Free Stanford ‘Intro to Cryptography’ Class Review

Last Spring I took my first coursera class, Introduction to Cryptogaphy taught by Dan Boneh. In college I took a few crypto classes, and I also deal with some crypto problems at work and in CTF. Although I’m definitely not a crypto expert, I had a pretty good background going into the class. Looking at the syllabus, I expected to work through a few interesting problems, but I didn’t expect to get too much out of it.

The class certainly exceeded my expectations. Here are the obvious things: Dan knows crypto backward and forward, and is a great teacher. The format was great – I liked being able to rewind videos at pieces I didn’t understand at first. The forum was also great – other students would answer my questions (I answered a few for other people also), and Dan himself would regularly chime in with answers to tricky problems people ran into.

One of the biggest reasons I think the class was so good was its focus on offense. I don’t really understand how defensive security people can try to defend stuff without understanding offense… yet the crypto classes I’d taken before tried to do exactly that. How was I supposed to understand why things needed to be done a certain way if I don’t know how it can break? Crypto books have been the same way – every crypto book I’ve read before (e.g. Bruce Schneier books) don’t seem to give much page space to offense. Dan brings the attacker’s perspective into every lecture, and I have a much better understanding of practical cryptography because of it.

I did manage to finish the class, but it was a lot more difficult than I expected (a good difficult :)) They seem to offer this class regularly, and I couldn’t recommend it more to anyone interested in cryptography.

Here are excerpts of my favorite problems he gave us to solve, and my solution for those problems. If you’re planning on taking the full class – spoiler alert. These questions might also be interesting if you don’t want to take an entire class, but just want to try and solve some super cool crypto problems. One note is all of these problems were optional, which was a decision made early on because he didn’t want programming to be a prerequisite. These problems are not required to get a coveted statement of accomplishment.

Week 1 – Two Time Pad (Reusing Stream Cipher Keys)

Problem:

“Let us see what goes wrong when a stream cipher key is used more than once. Below are eleven hex-encoded ciphertexts that are the result of encrypting eleven plaintexts with a stream cipher, all with the same stream cipher key. Your goal is to decrypt the last ciphertext, and submit the secret message within it as solution. ” These ciphertexts are (sorry for the poor formatting, but you should be able to copy them out):

ciphers = [
"315c4eeaa8b5f8aaf9174145bf43e1784b8fa00dc71d885a804e5ee9fa40b16349c146fb778cdf2d3aff021dfff5b403b510d0d0455468aeb98622b137dae857553ccd8883a7bc37520e06e515d22c954eba5025b8cc57ee59418ce7dc6bc41556bdb36bbca3e8774301fbcaa3b83b220809560987815f65286764703de0f3d524400a19b159610b11ef3e",
"234c02ecbbfbafa3ed18510abd11fa724fcda2018a1a8342cf064bbde548b12b07df44ba7191d9606ef4081ffde5ad46a5069d9f7f543bedb9c861bf29c7e205132eda9382b0bc2c5c4b45f919cf3a9f1cb74151f6d551f4480c82b2cb24cc5b028aa76eb7b4ab24171ab3cdadb8356f",
"32510ba9a7b2bba9b8005d43a304b5714cc0bb0c8a34884dd91304b8ad40b62b07df44ba6e9d8a2368e51d04e0e7b207b70b9b8261112bacb6c866a232dfe257527dc29398f5f3251a0d47e503c66e935de81230b59b7afb5f41afa8d661cb",
"32510ba9aab2a8a4fd06414fb517b5605cc0aa0dc91a8908c2064ba8ad5ea06a029056f47a8ad3306ef5021eafe1ac01a81197847a5c68a1b78769a37bc8f4575432c198ccb4ef63590256e305cd3a9544ee4160ead45aef520489e7da7d835402bca670bda8eb775200b8dabbba246b130f040d8ec6447e2c767f3d30ed81ea2e4c1404e1315a1010e7229be6636aaa",
"3f561ba9adb4b6ebec54424ba317b564418fac0dd35f8c08d31a1fe9e24fe56808c213f17c81d9607cee021dafe1e001b21ade877a5e68bea88d61b93ac5ee0d562e8e9582f5ef375f0a4ae20ed86e935de81230b59b73fb4302cd95d770c65b40aaa065f2a5e33a5a0bb5dcaba43722130f042f8ec85b7c2070",
"32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30ee714979c7e1123a8bd9822a33ecaf512472e8e8f8db3f9635c1949e640c621854eba0d79eccf52ff111284b4cc61d11902aebc66f2b2e436434eacc0aba938220b084800c2ca4e693522643573b2c4ce35050b0cf774201f0fe52ac9f26d71b6cf61a711cc229f77ace7aa88a2f19983122b11be87a59c355d25f8e4",
"32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd90f1fa6ea5ba47b01c909ba7696cf606ef40c04afe1ac0aa8148dd066592ded9f8774b529c7ea125d298e8883f5e9305f4b44f915cb2bd05af51373fd9b4af511039fa2d96f83414aaaf261bda2e97b170fb5cce2a53e675c154c0d9681596934777e2275b381ce2e40582afe67650b13e72287ff2270abcf73bb028932836fbdecfecee0a3b894473c1bbeb6b4913a536ce4f9b13f1efff71ea313c8661dd9a4ce",
"315c4eeaa8b5f8bffd11155ea506b56041c6a00c8a08854dd21a4bbde54ce56801d943ba708b8a3574f40c00fff9e00fa1439fd0654327a3bfc860b92f89ee04132ecb9298f5fd2d5e4b45e40ecc3b9d59e9417df7c95bba410e9aa2ca24c5474da2f276baa3ac325918b2daada43d6712150441c2e04f6565517f317da9d3",
"271946f9bbb2aeadec111841a81abc300ecaa01bd8069d5cc91005e9fe4aad6e04d513e96d99de2569bc5e50eeeca709b50a8a987f4264edb6896fb537d0a716132ddc938fb0f836480e06ed0fcd6e9759f40462f9cf57f4564186a2c1778f1543efa270bda5e933421cbe88a4a52222190f471e9bd15f652b653b7071aec59a2705081ffe72651d08f822c9ed6d76e48b63ab15d0208573a7eef027",
"466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31c9941cf110abbf409ed39598005b3399ccfafb61d0315fca0a314be138a9f32503bedac8067f03adbf3575c3b8edc9ba7f537530541ab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83",
"32510ba9babebbbefd001547a810e67149caee11d945cd7fc81a05e9f85aac650e9052ba6a8cd8257bf14d13e6f0a803b54fde9e77472dbff89d71b57bddef121336cb85ccb8f3315f4b52e301d16e9f52f904"
]

Solution

The most important piece of this is to realize that XORing the ciphertexts together produces the xor of the plaintexts. Additionally, if you can guess at the next character for a given row, you can xor the ciphertext with what it should be to produce the key.

For example, if the ciphertext were 89 and the letter should be ‘e’, then

>>> hex(ord('e') ^ 0x89)

would equal the key. You can apply this key to all rows and when you get it wrong, everything looks wonky.

So to demonstrate, the first step is to get a foothold. I postulated 32510b was “the” because it was repeated several times at the beginning and ‘the’ is the most common trigram. Applying this as a key, everything looked correct (try another common one, like ‘and’, and it will look off). I went one key at a time from there, using the following program.

#!/usr/bin/python

import sys
from optparse import OptionParser


#ciphers = ... #found above

class twotimepad:
    
    def __init__(self):
        #based on what we know so far...
        self.keysofar = [0x46, 0x39, 0x6e]



    def get_freq(self, charArray):
        letterdict = {}
        for i in charArray:
            try:
                letterdict[i] += 1
            except KeyError:
                letterdict = 1
        return letterdict

    def print_mSoFar(self):
        c_sofar = [i[0:len(self.keysofar)*2] for i in ciphers]
        for i in range(0,11):
            sys.stdout.write(str(i) + ".\t")
            for j in range(0, len(self.keysofar)):
                a = self.keysofar[j];
                b = int(c_sofar[i][j*2:j*2+2], 16)
                sys.stdout.write(chr(self.keysofar[j] ^ int(c_sofar[i][j*2:j*2+2], 16)))
            print ""

    def getnextchar(self, i):        
        nextchar = ciphers[i]
        nextchar = nextchar[len(self.keysofar)*2:len(self.keysofar)*2+2]       
        return nextchar
        
    def print_next_letter(self):
        for i in range(0,11):
            print (str(i) + ":\t"+ self.getnextchar(i))

    def add_key(self, num, letter='a'):
        if num == -1:
            self.keysofar = self.keysofar[:-1]
        else:
            self.keysofar.append(ord(letter) ^ int(self.getnextchar(num), 16))
            
    def run(self):        
        while 1:
            print "Current KEY"
            print self.keysofar
            print ("\r\nStuff so Far")
            self.print_mSoFar()
            print "\r\nNext Letter"
            #self.print_next_letter()
            num = int(raw_input("\r\n\r\nEnter next number (-1 for mistake): "))
            letter = raw_input("Enter letter: ")
            self.add_key(num, letter)
    
m = twotimepad()
m.run()

This makes a program where you get a shell thing to eyeball one character at a time.

The final key was the following:

Key = [70, 57, 110, 137, 201, 219, 216, 204, 152, 116, 53, 42, 205, 99, 149, 16, 46, 175, 206, 120, 170, 127, 237, 40, 160, 127, 107, 201, 141, 41, 197, 11, 105, 176, 51, 154, 25, 248, 170, 64, 26, 156, 109, 112, 143, 128, 192, 102, 199, 99, 254, 240, 18, 49, 72, 205, 216, 232, 2, 208, 91, 169, 135, 119, 51, 93, 174, 252, 236, 213, 156, 67, 58, 107, 38, 139, 96, 191, 78, 240, 60, 154, 97]

And the final secret message was:

the secret message is: When using a stream cipher, never use the key more than once

Week 1 – Breaking a Linear Congruential Generator

Problem:

The PRG described below uses a 56-bit secret seed. Running the program generates the following first nine outputs of the PRG:

output #1: 210205973
output #2: 22795300
output #3: 58776750
output #4: 121262470
output #5: 264731963
output #6: 140842553
output #7: 242590528
output #8: 195244728
output #9: 86752752

Show that this PRG is insecure by computing the next output. What is the next output (output #10) of the PRG? Note that you are not given the seed.

import random

P = 295075153L   # about 2^28

class WeakPrng(object):
    def __init__(self, p):   # generate seed with 56 bits of entropy
        self.p = p
        self.x = random.randint(0, p)
        self.y = random.randint(0, p)
   
    def next(self):
        # x_{i+1} = 2*x_{i}+5  (mod p)
        self.x = (2*self.x + 5) % self.p

        # y_{i+1} = 3*y_{i}+7 (mod p)
        self.y = (3*self.y + 7) % self.p

        # z_{i+1} = x_{i+1} xor y_{i+1}
        return (self.x ^ self.y) 


prng = WeakPrng(P)
for i in range(1, 10):
  print "output #%d: %d" % (i, prng.next())

Solution

This looks like a Linear Congruential generator. from wikipedia: The period of a general LCG is at most m, and for some choices of a much less than that. Provided that c is nonzero, the LCG will have a full period for all seed values if and only if:[2]

The most important piece is maybe that it’s linear. Realize the following algorithm will take only about 2^28 guesses, one for every x.

For each x[i]:
  calculate what y[i] has to be, given that x[i] ^ y[i] = output[i]
  see if x[i+1] ^ y[i+1] == output[i+1]. If so, iterate, and we have a match

The following C# program calculates this very quickly, on my machine about five seconds.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace linear_prng
{
    class Program
    {


        static void Main(string[] args)
        {
            const int MAX = 295075153;
            int[] seq = new int[] { 210205973, 22795300, 58776750, 121262470, 264731963, 140842553, 242590528 };


            for (int x = 0; x < MAX; x++)
            {
                int x_temp = x;
                for (int i=0; i < seq.Length-1; i++)
                {
                    
                    int y = x_temp ^ seq[i];
                    int x_next = (2 * x_temp + 5) % MAX;
                    int y_next = (3 * y + 7) % MAX;
                    if (seq[i + 1] == (x_next ^ y_next))
                    {
                        System.Console.WriteLine("{0}: Sol x {1} {2}", i, x_temp, y);
                        x_temp = x_next;
                        y = y_next;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            System.Console.ReadLine();
            
        }
    }
}

Plug the output into the original python program in place of the random x and y, and calculate the next number, which is: 231886864

Week 2 – Insecurity of a Two Round Feistel

Problem

Recall that the Luby-Rackoff theorem discussed in Lecture 3.2 states that applying a three round Feistel network to a secure PRF gives a secure block cipher. Let’s see what goes wrong if we only use a two round Feistel. Let F:K×{0,1}32→{0,1}32 be a secure PRF. Recall that a 2-round Feistel defines the following PRP F2:K2×{0,1}64→{0,1}64:

Here R0 is the right 32 bits of the 64-bit input and L0 is the left 32 bits.

One of the following lines is the output of this PRP F2 using a random key, while the other three are the output of a truly random permutation f:{0,1}64→{0,1}64. All 64-bit outputs are encoded as 16 hex characters. Can you say which is the output of the PRP? Note that since you are able to distinguish the output of F2 from random, F2 is not a secure block cipher, which is what we wanted to show.

Hint: First argue that there is a detectable pattern in the xor of F2(⋅,064) and F2(⋅,132032). Then try to detect this pattern in the given outputs.

Then it gives some sample inputs and outputs

On input 0^64 the output is “2d1cfa42 c0b1d266”. On input 1^32 0^32 the output is “eea6e3dd b2146dd0”.
On input 064 the output is “7c2822eb fdc48bfb”. On input 132032 the output is “325032a9 c5e2364b”.
On input 064 the output is “290b6e3a 39155d6f”. On input 132032 the output is “d6f491c5 b645c008”.
On input 064 the output is “9d1a4f78 cb28d863”. On input 132032 the output is “75e5e3ea 773ec3e6”.

Solution

In the first round 0 is xored with the F(k1) and in the second 1 is xored with F(k1) so just looking at the first block, xor that with one and it should give us the first block of the second

This simple program does that xor

import sys

a = sys.argv[1].decode("hex")
for i in a:
sys.stdout.write("{0:02x} ".format(ord(i)^0xff))

print ""

Week 3 – Hash Collision

Problem

In this assignment your task is to find hash function collisions using the birthday attack discussed in the lecture.

Consider the hash function obtained by truncating the output of SHA256 to 50 bits, say H(x)=LSB50(SHA256(x)), that is we drop all but the right most 50 bits of the output. Your goal is to find a collision on this hash function. Find two strings x≠y such that LSB50(SHA256(x))=LSB50(SHA256(y)) and then enter the hex encoding of these strings in the fields below.

For an implementation of SHA256 use an existing crypto library such as PyCrypto (Python), Crypto++ (C++), or any other.

Solution

This code takes a few minutes, but it eventually finds a collision.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;
using System.Data.SqlServerCe;



namespace hash_collision
{
    class Program
    {
        //given a seed, returns the first 50 byte hash
        //woops, the assignment asks for the last
        static Int64 getTruncatedHash(int seed)
        {
            SHA256 shaM = new SHA256Managed();
            byte[] result = shaM.ComputeHash(BitConverter.GetBytes(seed));

            byte[] truncatedresult = new byte[8];
            Array.Copy(result, truncatedresult, 8);
            //last byte only car about two most significant bits, do & 0xB0
            truncatedresult[6] = (byte)(truncatedresult[6] & 0xB0);
            truncatedresult[7] = (byte)(0x00);
            return (BitConverter.ToInt64(truncatedresult, 0));

        }


        //given a seed, returns the last 50 byte hash
        static Int64 getEncatedHash(int seed)
        {
            SHA256 shaM = new SHA256Managed();
            byte[] result = shaM.ComputeHash(BitConverter.GetBytes(seed));

            byte[] truncatedresult = new byte[8];
            //Array.Copy(result, 0, truncatedresult, 23, 8);
            Array.Copy(result, 24, truncatedresult, 0, 8);
            //last byte only care about two least significant bits, do & 0x03
            truncatedresult[1] = (byte)(truncatedresult[1] & 0x03);
            truncatedresult[0] = (byte)(0x00);
            return (BitConverter.ToInt64(truncatedresult, 0));

        }

        static void printStuff(int val)
        {
            System.Console.Write("sha256(");
            byte[] seed = BitConverter.GetBytes(val);
            foreach (int i in seed)
            {
                System.Console.Write("{0:X2}", i); 
            }
            System.Console.Write(")\t");
            SHA256 shaM = new SHA256Managed();
            byte[] result = shaM.ComputeHash(seed);
            foreach (int i in result)
            {
                System.Console.Write("{0:X2}", i);
            }
            System.Console.Write("\r\n");
        }


        static void Main(string[] args)
        {

            for(int iter=0; iter<24; iter++)
            {
                Dictionary<Int64, int> mhash = new Dictionary<Int64, int>();

                //I'd much rather do 2^25, but .net throws an outofmemoryexception... too bad it's not config
                //something like Java -xMx2G, which would be nice.
                int scaler = (int)Math.Pow(2, 24);
                for (int i = scaler*iter; i < scaler*(iter+1); i++)
                {
                    Int64 fiftyhash = getEncatedHash(i);
                    if (mhash.ContainsKey(fiftyhash))                   {
                        System.Console.WriteLine("FOUND!!!!");
                        printStuff(i);
                        printStuff(mhash[fiftyhash]);
                        Environment.Exit(0);
                    }
                    else
                        mhash.Add(fiftyhash, i);

                }
                System.Console.WriteLine("Done with iteration {0} :(", iter);
                System.Threading.Thread.Sleep(500);
            }
        }
    }
}

Week 4 – CBC with IV

Problem:

An attacker intercepts the following ciphertext (hex encoded):

   20814804c1767293b99f1d9cab3bc3e7 ac1e37bfb15599e5f40eef805488281d 

He knows that the plaintext is the ASCII encoding of the message “Pay Bob 100$” (excluding the quotes). He also knows that the cipher used is CBC encryption with a random IV using AES as the underlying block cipher. Show that the attacker can change the ciphertext so that it will decrypt to “Pay Bob 500$”. What is the resulting ciphertext (hex encoded)? This shows that CBC provides no integrity.

Solution:

This is insecure because the first message block is xored with the random IV

20814804c1767293b99f1d9cab3bc3e7 ac1e37bfb15599e5f40eef805488281d
P a y B o b 1 0 0 $

9th char
0xb9 decrypts to 1
0xb9 xor ascii (1 xor 5)
0xb9 xor 0x31 xor 0x35
= 0xbd

20814804c1767293bd9f1d9cab3bc3e7 ac1e37bfb15599e5f40eef805488281d

Week 4 – Padding Oracle

Problem:
 
A web site administrator found these log entries in a web server log. After some digging, the admin realized that the first log entry is an AES CBC encryption with random IV of some secret data (the ciphertext is hex encoded and appears right after the “GET /”). The secret data contains private user data that should only be known to the web site. 

After more digging the admin realized that the web site is vulnerable to a CBC padding oracle attack. In particular, when a decrypted CBC ciphertext ends in an invalid pad the web server returns a 403 error code (forbidden request). When the CBC padding is valid, but the message is malformed the web server returns a 404 error code (URL not found). To her horror, the admin realized that the log entries following the first entry are a result of a remote CBC padding oracle attack on the ciphertext in the first log entry. 

See if you can use the given log entries to recover the decryption of the ciphertext in the first log entry. Keep in mind that the first ciphertext block is the random IV. The decrypted message is ASCII encoded. 

Solution:

There are plenty of good resources about the padding oracle. My favorite is probably this: http://blog.gdssecurity.com/labs/2010/9/14/automated-padding-oracle-attacks-with-padbuster.html

#!/usr/bin/python
import sys

class oracleAnal:
    #Original doc at http://spark-university.s3.amazonaws.com/stanford-crypto/projects/proj4-log.txt
    #The file processed here generated with cat ./proj4-log.txt | egrep " 404" | cut -f2 -d/ | cut -f1 -d " " > pad.txt
    def __init__(self, fname, debug=False):
      self.debug = debug
      self.iv = []
      self.requests = []
      #need to skip the iv (e.g. block 0)
      self.currBlock = 1
      self.parseRequests(fname)  
      for i in self.iv:
        self.decryptBlock(self.requests[16*self.currBlock:16*(self.currBlock+1)], i)
        self.currBlock += 1
    
    #this parses the request file into self.iv and self.requests
    def parseRequests(self, fname):
      f = open(fname)
      requests = f.readlines()
      for i in range(0, len(requests)):
        req = requests[i].strip()
        self.requests.append(req[:32])
        if(i % 16 == 0):
          self.iv.append(req[32:])
      f.close()
      
    #takes a string, decodes it, and splits it to a byte array  
    def decodestr(self, mstr):
      #blocks should be 16 bytes
      if(len(mstr) != 32):
        print "Error"
      mstr = mstr.decode("hex")
      s = [ord(ch) for ch in mstr]
      return s
      
    #each block in the list is of the 16 byte format like
    #e.g. 202020202020202020202020202020d8
    #and iv is the previous original 16 byte crypt block
    #e.g. cac544d7942e50e1a0afa156c803d115
    def decryptBlock(self, bList, iv):
        finalBstr = ""
        if self.debug:
            print "Decrypting a block with IV ", iv
        iv = self.decodestr(iv)
        for block in bList:
            decblock = self.decodestr(block)
            for i in range(0,len(decblock)):
                byte = decblock[i]
                #error here if the valid pad found is 0x20, but can manually fix later...
                #plus it's right 255/256 times :)
                if byte == 0x20:
                    continue
                pad = byte
                padRes = 16-i
                tiv = iv[i]
                if self.debug:
                    print hex(pad), hex(padRes), hex(tiv)
                    print chr(pad ^ padRes ^ tiv)
                finalBstr = chr(pad ^ padRes ^ tiv) + finalBstr
                break
        sys.stdout.write(finalBstr)


m = oracleAnal("pad.txt")

Week 5 – Meet in the Middle

Problem (shortened to take out extras since formatting was messed up in copy)

Your goal this week is to write a program to compute discrete log modulo a prime p. Let g be some element in Z∗p and suppose you are given h in Z∗p such that h=g^x where 1≤x≤240. Your goal is to find x. More precisely, the input to your program is p,g,h and the output is x.

The trivial algorithm for this problem is to try all 2^40 possible values of x until the correct one is found, that is until we find an x satisfying h=g^x in Zp. This requires 2^40 multiplications. In this project you will implement an algorithm that runs in time roughly 240−−−√=220 using a meet in the middle attack.

(he gives an algorithm)

Now that we have an algorithm, here is the problem to solve:

p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
g = 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568
p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171

Each of these three numbers is about 153 digits. Find x such that h=g^x in Zp.

Solution

This was pretty straightforward.

import gmpy2


p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
g = 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568
p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171

def calc1(i):
    denominv = pow(g, i, p)
    denom = gmpy2.invert(denominv, p)
    tval = gmpy2.mul(h, denom)
    retval = gmpy2.f_mod(tval, p)
    return retval

def calc2(i):
    return pow(g, (2**20)*i, p)

hasht = {}
for i in range(0,2**20):
    hasht[calc1(i)] = i
for i in range(0, 2**20):
    c2 = calc2(i)
    if c2 in hasht:
        print "x0: ", i
        print "x1: ", hasht[c2]
        break

x = (((357984 * 2**20) + 787046)% p)
print x

Week 6 – RSA Poor Primes

Problem

Your goal in this project is to break RSA when the public modulus N is generated incorrectly. This should serve as yet another reminder not to implement crypto primitives yourself.

Normally, the primes that comprise an RSA modulus are generated independently of one another. But suppose a developer decides to generate the first prime p by choosing a random number R and scanning for a prime close by. The second prime q is generated by scanning for some other random prime also close to R. We show that the resulting RSA modulus N=pq can be easily factored.

Suppose you are given a composite N and are told that N is a product of two relatively close primes p and q, namely p and q satisfy
|p−q|<2N^(1/4) (*)
Your goal is to factor N.

Factoring challenge #1: The following modulus N is a products of two primes p and q where |p−q|<2N^(1/4). Find the smaller of the two factors and enter it as a decimal integer.

N = 17976931348623159077293051907890247336179769789423065727343008115 \
    77326758055056206869853794492129829595855013875371640157101398586 \
    47833778606925583497541085196591615128057575940752635007475935288 \
    71082364994994077189561705436114947486504671101510156394068052754 \
    0071584560878577663743040086340742855278549092581

Factoring challenge #2: The following modulus N is a products of two primes p and q where |p−q|<2^11*N^(1/4). Find the smaller of the two factors and enter it as a decimal integer.

N = 6484558428080716696628242653467722787263437207069762630604390703787 \
    9730861808111646271401527606141756919558732184025452065542490671989 \
    2428844841839353281972988531310511738648965962582821502504990264452 \
    1008852816733037111422964210278402893076574586452336833570778346897 \
    15838646088239640236866252211790085787877

Factoring challenge #3: (extra credit) The following modulus N is a products of two primes p and q where |3p−2q|<N^(1/4). Find the smaller of the two factors and enter it as a decimal integer.

N = 72006226374735042527956443552558373833808445147399984182665305798191 \
    63556901883377904234086641876639384851752649940178970835240791356868 \
    77441155132015188279331812309091996246361896836573643119174094961348 \
    52463970788523879939683923036467667022162701835329944324119217381272 \
    9276147530748597302192751375739387929

Solution

I only solved 1 and 2

import gmpy2
import math


class bad_rsa:
    def __init__(self, N):
        self.N = N
        self.computePrime()

    def computePrime(self):
        for i in range (1, 2**20):
            self.A = gmpy2.isqrt(self.N) + i
            self.calcX()
            if self.verify():
                print "found it!"
                print self.p
                break

    def calcX(self):
        Asquared = gmpy2.mul(self.A, self.A)
        remainder = gmpy2.sub(Asquared, self.N)
        self.x  = gmpy2.isqrt_rem(remainder)[0] 

    def verify(self):
        self.p = gmpy2.sub(self.A, self.x)
        self.q = gmpy2.add(self.A ,self.x)
        if gmpy2.mul(self.p, self.q) == self.N:
            return True
        else:
            return False


#problem 1
prob1 = gmpy2.mpz('17976931348623159077293051907890247336179769789423065727343008115' +
                   '77326758055056206869853794492129829595855013875371640157101398586' +
                   '47833778606925583497541085196591615128057575940752635007475935288' +
                   '71082364994994077189561705436114947486504671101510156394068052754' +
                   '0071584560878577663743040086340742855278549092581')
#problem 2
prob2 = gmpy2.mpz('6484558428080716696628242653467722787263437207069762630604390703787' +
                  '9730861808111646271401527606141756919558732184025452065542490671989' +
                  '2428844841839353281972988531310511738648965962582821502504990264452' +
                  '1008852816733037111422964210278402893076574586452336833570778346897' +
                  '15838646088239640236866252211790085787877')

a = bad_rsa(prob2)
raw_input("Enter Key")