贴下RSA的code 出自from Hacking secret ciphers with PYthon

我总是说，要了解RSA，首先你应该有两个很大的质数．　

Generating Public and Private Keys
A key in the RSA scheme is made of two numbers. There are three steps to creating the
keys:
1. Create two random, very large prime numbers. These numbers will be called p and q.
Multiply these numbers to get a number which we will call n.
2. Create a random number, called e, which is relatively prime with (p – 1) × (q – 1).
3. Calculate the modular inverse of e. This number will be called d.
The public key will be the two numbers n and e. The private key will be the two numbers
n and d. (Notice that both keys have the number n in them.) We will cover how to encrypt
and decrypt with these numbers when the RSA cipher program is explained. First let’s
write a program to generate these keys.

import random
import sys
import os
import rabinMiller
import cryptMath

def main():
    #create a public/private keypair with 1024 bit keys
    print("Making key files...")
    makeKeyFiles("al_sweigart", 1024)
    print("Key files made")


def generateKey(keySize):
    #create a public/private key pair with keys that are keySize bits in
    #size, This function may take a while to run.

    #step 1: create two primes number, p and q , Calculate n = p * q
    print("Generating a prime...")
    p = rabinMiller.generateLargePrime(keySize)
    print("Generating q prime...")
    q = rabinMiller.generateLargePrime(keySize)
    n = p * q

    #step 2: create a number e that is relatively prime to (p-1)*(q-1)
    print("Generating e that is relatively prime to (p-1)*(q-1)...")
    while True:
        #keep trying random number for e untile one is valid
        e = random.randrange(2 ** (keySize-1), 2**(keySize))

        if cryptMath.gcd(e, (p-1)*(q-1)) == 1:
            break

    #step 3, Calculate d, the mod inverse of e
    print("Calculating d that is mod inverse of e...")

    d = cryptMath.findModInverse(e, (p-1)*(q-1))

    publicKey=(n, e)
    privateKey = (n, d)

    print("Pubic key:", publicKey)
    print("Private key:", privateKey)

    return (publicKey, privateKey)

def makeKeyFiles(name, keySize):
    #create two files "x_pubkey.txt" and "x_privkey.txt"
    #where x is the value in name) with the n,e and d,e
    #integers written in them. delimited by a comma

    #our safety check will prevent us from overwriting our old key file
    if os.path.exists("{}_pubkey.txt".format(name)) or \
        os.path.exists("{}_privkey.txt".format(name)) :

        sys.exit("Warning: The file {}_pubkey.txt or {}_privkey.txt already exists! use a different name or delete\
            these files and re-run this program. ".format(name, name))

    publicKey, privateKey = generateKey(keySize)

    print()
    print("The public key is {} and a {} digit number".format(len(str(publicKey[0])), len(str(publicKey[1]))))

    print("Writing public key to file {}_pubkeytxt".format(name))

    fo = open("{}_pubkey.txt".format(name), "w")
    fo.write("{},{},{}".format(keySize, publicKey[0],publicKey[1]))

    fo.close()
    print()

    print("The private key is a {} and a {} digit number.".format(len(str(privateKey[0])), len(str(privateKey[1]))))
    print("writing privae key to file {}_privkey.txt".format(name))
    fo = open("{}_privkey.txt".format(name), "w")
    fo.write("{},{},{}".format(keySize, privateKey[0],privateKey[1]))

    fo.close()



if __name__== "__main__":
    main()

其中import的rabinMiller.py是rabinMiller算法来找到一个很大的质数．

import random

def rabinMiller(num):
    #returns True if num is a prime number

    s = num -1
    t =0
    while s % 2 ==0:
        #keep halving s while it is even(and use t
        #to count how many times we halve s)

        s = s // 2
        t += 1


    for trials in range(5): #try to falsify num primality 5 times
        a = random.randrange(2, num -1)
        v = pow(a,s,num)

        if v != 1: #this test does not apply if v is 1
            i=0
            while v != (num -1):
                if i==t -1:
                    return False
                else:
                    i += 1
                    v = (v**2) % num
    return True

def isPrime(num):
    #Return true if num is a prime number, This function does a quicker
    #prime number check before calling rabinMiller()

    if (num < 2):
        return False        #0,1 and negative numbers are not prime

    # About 1/3 of the time we can quickly determine if num is not prime
    # by dividing by the first few dozen prime numbers. This is quicker
    # than rabinMiller(), but unlike rabinMiller() is not guaranteed to
    # prove that a number is prime.
    lowPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

    if num in lowPrimes:
        return True

    #see if any of the low prime numbers can divide num
    for prime in lowPrimes:
        if (num %  prime == 0):
            return False

    #if all else fails, call rabinMaller() to determine if num is a prime
    return rabinMiller(num)


def generateLargePrime(keysize = 1024):

    #return a random prime number of keysize bits in size
    while True:
        num = random.randrange(2**(keysize-1), 2**(keysize))
        if isPrime(num):
            return num

最后就是使用生成的key来encrypt/decrypt 一些text 然后写入文件或者读取出来．

import sys

#IMPORTANT: The block size MUST be less than or equal to the key
##(Note: The block size is in bytes, the key size is in bits, There
#are 8 bits in 1 byte . )

DEFAULT_BLOCK_SIZE = 128 #bytes
BYTE_SIZE = 256     #one byte has 256 different values

def main():

    #Run a test that encrypts a message to a file or decrypts a message from a file
    filename = "encrypted_file.txt" #The file to write to /read from
    mode = "decrypt" #set to encrypt or decrypt

    if mode == "encrypt":
        message = '''"Journalists belong in the gutter because that is where the ruling classes throw their guilty secrets." -Gerald Priestland "The Founding Fathers gave the free press the protection it must have to bare the secrets of government and inform the people." -Hugo Black'''
        publicKeyFileName = "al_sweigart_pubkey.txt"
        print("Encrypting and writing to {}".format(filename))
        encryptedText = encryptAndWriteToFile(filename, publicKeyFileName, message)

        print("Encrypted text:")
        print(encryptedText)

    elif mode == "decrypt":
        privKeyFileName = "al_sweigart_privkey.txt"
        print("Reading from {} and decrypting ".format(filename))
        decryptedText = readFromFileAndDecrypt(filename, privKeyFileName)

        print("Decrypted text:")
        print(decryptedText)

def getBlocksFromText(message, blockSize = DEFAULT_BLOCK_SIZE):
    #convert a string message to a list of block integers, Each integer
    #represents 128 ( or whatever blocksize is set to )string characters.
    messageBytes = message.encode("ascii") #convert the string to bytes

    blockInts = []

    for blockStart in range(0, len(messageBytes), blockSize):
        #calculate the block integer for this block of text
        blockInt = 0
        for i in range(blockStart, min(blockStart + blockSize, len(messageBytes))):
            blockInt += messageBytes[i] * (BYTE_SIZE ** (i % blockSize))

        blockInts.append(blockInt)

    return blockInts


def getTextFromBlocks(blockInts, messageLength, blockSize=DEFAULT_BLOCK_SIZE):
    #convert a list of block integers to the original message string
    #The original message length is needed to properly convert the last block integer
    message = []
    for blockInt in blockInts:
        blockMessage = []
        for i in range(blockSize -1 , -1 , -1):
            if len(message) + i < messageLength:
                #Decode the message string for the 128 (or whatever
                #blocksize is set to ) characters from this block integer
                asciiNumber = blockInt // (BYTE_SIZE ** i)
                blockInt = blockInt % (BYTE_SIZE ** i)
                blockMessage.insert(0, chr(asciiNumber))

        message.extend(blockMessage)
    return "".join(message)


def encryptMessage(message, key, blockSize = DEFAULT_BLOCK_SIZE):
    #convert the message string into a list of block integers, and then
    #encrypt each block integer. Pass the PUBLIC key to encrypt
    encryptedBlocks = []
    n , e = key

    for block in getBlocksFromText(message, blockSize):
        #ciphertext = plaintext ^ e mod n
        encryptedBlocks.append(pow(block, e, n))

    return encryptedBlocks


def decryptMessage(encryptedBlocks, messageLength, key, blockSize = DEFAULT_BLOCK_SIZE):
    #Decrypt a list of encrypted block ints into the orginal message String
    #The original message length is required to properly decrypt
    #The last block, Be sure to pass the PRIVATE key to decrypt
    decryptedBlocks = []
    n, d = key
    for block in encryptedBlocks:
        #plainText = cipher ^ d mode n
        decryptedBlocks.append(pow(block , d, n ))

    return getTextFromBlocks(decryptedBlocks, messageLength, blockSize)

def readKeyFile(keyFileName):
    #given the filename of a file that contains a public or private key,
    #return the key as a (n, e) or (n, d) tuple value
    fo = open(keyFileName)
    content = fo.read()
    fo.close()

    keySize, n, EorD = content.split(",")
    return (int(keySize),int(n), int(EorD))


def encryptAndWriteToFile(messageFilename, keyFilename, message, blockSize=DEFAULT_BLOCK_SIZE):
    #Using a key from a key file, encrypt the message and save it to a file
    #Returns the encrypted message string
    keySize, n, e = readKeyFile(keyFilename)

    #check the key size is greater than block size
    if keySize < blockSize * 8: # *8 to convert bytes to bits
        sys.exit("ERROR: Block size is {} bits and key size is {} bits. The RSA\
        cipher requires the block size to be equal to or less than the key size\
        Either increase the block size or use different keys.".format(blockSize * 8, keySize))

    #encrypt the message
    encryptedBlocks = encryptMessage(message, (n , e), blockSize)

    #convert the large int value to one string value
    for i in range(len(encryptedBlocks)):
        encryptedBlocks[i] = str(encryptedBlocks[i])
    encryptedContent = ','.join(encryptedBlocks)


    #write out the encrypted string to the output file
    encryptedContent = "{}_{}_{}".format(len(message), blockSize, encryptedContent)

    fo = open(messageFilename, "w")
    fo.write(encryptedContent)
    fo.close()
    #Also return the encrypted string
    return encryptedContent


def readFromFileAndDecrypt(messageFilename, keyFilename):
    #using a key from a key file, read an encrypted message from a file
    #and then decrypt it, returns the decrypted message string
    keySize , n , d = readKeyFile(keyFilename)

    #Read in the message length and the encrypted message from the file
    fo = open(messageFilename)
    content = fo.read()
    messageLength,blockSize, encryptedMessage = content.split("_")
    messageLength = int(messageLength)
    blockSize = int(blockSize)

    #check the key size is greater than block size
    if keySize < blockSize * 8:
        sys.exit("ERROR: Block size is {} bits and key size is {} bits. The RSA\
        cipher requires the block size to be equal to or less than the key size\
        .Either increase the block size or use different keys.".format(blockSize * 8, keySize))

    #convert the encrypted message into large int values
    encryptedBlocks = []
    for block in encryptedMessage.split(','):
        encryptedBlocks.append(int(block))

    #decrypt the large int values
    return decryptMessage(encryptedBlocks, messageLength, (n, d), blockSize)

#main() function
if __name__=="__main__":
    main()