RSA-Verschlüsselung in Python

#coding: latin1

'''
Created on 05.12.2009

@author: Lars Heppert
'''


def multi(x, y):
    '''Multiplizieren durch Addieren und Verdoppeln'''
    result = 0
    while y > 0:
        if y % 2 == 1:
            # bei ungerade Werten fuer die 2. Zahl wird
            # die das Zwischenergebnis der 1. Zahl summiert
            result += x
            # die Reduzierung um 1 macht die 2. Zahl wieder gerade
            # und verhindert einen Rest bei der Division durch 2,
            # wobei es hier nur darum geht in den else-Zweig zu wechseln
            y -= 1       
        else:
            x *= 2
            y /= 2
            
    return result

print multi(31, 74)

def pot(x,y):
    '''Potenzieren durch Quadrieren und Multiplizieren'''
    result = 1
    while y > 0:
        if y % 2 == 1:
            result *= x
            y -= 1
        else:
            y /= 2
            x *= x

    return result

print pot(2, 4)

def modpot(x,y,n):
    '''
    Schnelles Potenzieren x^y (mod n)
    nach der Methode "square and multiply".
    Zwischenergebnisse werden modulo n reduziert
    '''
    result = 1
    while y > 0:
        if y % 2 == 1:
            result *= x
            result %= n
            y -= 1
        else:
            x *= x
            x %= n
            y /= 2
        
    return result

def xggt(a,b):
    x1, x2, y1, y2 = 1, 0, 0, 1
    while b:
        q = a // b
        x1, x2, y1, y2 = x2, x1 - q * x2, y2, y1 - q * y2
        a, b = b , a % b
        
    return a, x1, y1

print "xggt = ", xggt(23, 120)

import math
def isprime(n):
    if n % 2 == 0 and not n == 2:
        return (False)
    else:
        limit = int(math.sqrt(n)) + 1
        
    for l in range(3, limit, 2):
        if n % l == 0:
            return (False)

    return (True)

print isprime(23), "ist eine Primzahl"

import sys
import random

def toBinary(n):
    """
    toBinary(n)
    wandelt n in eine Liste, welche die Binärdarstellung
    von n repräsentiert - diese Darstellung vereinfacht
    die folgenden Schritte bzgl. der Primzahlprüfung
    """
    r = []
    while (n > 0):
        r.append(n % 2)
        n = n / 2
        
    return r

def test(a, n):
    """
    test(a, n)
    überprüft, ob n (einfach) zusammengestezt ist,
    also als Produkt anderer Zahlen entsteht
    """
    b = toBinary(n - 1)
    d = 1
    for i in xrange(len(b) - 1, -1, -1):
        x = d
        d = (d * d) % n
        if d == 1 and x != 1 and x != n - 1:
            return True
        if b[i] == 1:
            d = (d * a) % n
        if d != 1:
            return True

    return False

def MillerRabin(n, s = 50):
    """
      MillerRabin(n, s = 1000)
      überprüft, ob n prim ist
    """
    for j in xrange(1, s + 1):
        a = random.randint(1, n - 1)
        if (test(a, n)):
            return False # n is complex
        
    return True # n is prime

'''
Created on 07.12.2009

@author: GWV7FD3
'''

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    
    return a
    
print gcd(48, 16)

def extgcd(a, b):
    u = t = 1
    v = s = 0
    while b > 0:
        q = a // b
        a, b = b, a - q * b
        u, s = s, u - q * s
        v, t = t, v - q * t
        
    return a, u, v

print extgcd(48, 16)

def toBinary(n):
    r = []
    while (n > 0):
        r.append(n % 2)
        n = n / 2

    return r

def test(a, n):
    b = toBinary(n - 1)
    d = 1
    for i in xrange(len(b) - 1, -1, -1):
        x = d
        d = (d * d) % n
        if d == 1 and x != 1 and x != n - 1:
            return True
        if b[i] == 1:
            d = (d * a) % n
    if d != 1:
        return True
    
    return False

import random
def MillerRabin(n, s = 50):
    for j in xrange(1, s + 1):
        a = random.randint(1, n - 1)
        if (test(a, n)):
            return False
    return True

#bigNumbers = []
#for x in range(1000):
#    bigNumbers.append(random.getrandbits(random.randint(4200, 4600)))
#
#x = 0
#for number in bigNumbers:
#    x += 1
#    isPrime = MillerRabin(number)
#    print x
#    if isPrime:
#        print number, "is prime"
        
    
def extended_gcd(a, b):
    x, last_x = 0, 1
    y, last_y = 1, 0
 
    while b:
        quotient = a // b
        a, b = b, a % b
        x, last_x = last_x - quotient*x, x
        y, last_y = last_y - quotient*y, y
 
    return (last_x, last_y, a)
 
def inverse_mod(a, m):
    x, q, gcd = extended_gcd(a, m)
 
    if gcd == 1:
        # x is the inverse, but we want to be sure a positive number is returned.
        return (x + m) % m
    else:
        # if gcd != 1 then a and m are not coprime and the inverse does not exist.
        return None

        
def findMultiplicativeInverse(p, q, e):
    phi = (p - 1) * (q - 1)
    while gcd(phi, e) > 1:
        e += 2
    
    d = inverse_mod(e, phi)
    
    return d

def modPow(a, b, n):
    z = 1
    while b != 0:
        while (b % 2) == 0:
            b = b / 2
            a = (a * a) % n

        b = b - 1
        z = (z * a) % n

    return z

#    private boolean isQualityPrime(BigInteger p) {
#        BigInteger two = new BigInteger("2");
#        
#        int            x    = p.bitLength();
#        BigInteger    b    = two.pow(x);
#        while (b.compareTo(p) < 0) {
#            x++;
#            b = two.pow(x);
#        }
#        BigInteger    s    = two.pow(--x);
#        
#        boolean isEasyBiggerPrime    = (b.subtract(BigInteger.ONE)).equals(p) ? true : false;
#        boolean isEasySmallerPrime    = (s.add(BigInteger.ONE).equals(p)) ? true : false;
#        
#        if (isEasyBiggerPrime || isEasySmallerPrime) {
#            System.out.println("WARNING: Prime is near to 2^x!");
#            System.out.println("p = " + p);
#        }
#        
#        return !(isEasyBiggerPrime || isEasySmallerPrime);
#    }

import math
def isQualityPrime(p):
    bitLength   = math.floor(math.log(p, 2))
    powNum      = 2**bitLength
    while powNum < p:
        bitLength  += 1
        powNum      = 2**bitLength
    
    
isQualityPrime(3000)

def strToNumber(text):
    x       = 1
    number  = 0
    for zeichen in text:
        number  += ord(zeichen)*x
        x       *= 256
        
    return number

def numberToStr(number):
    text = []
    while number > 0:
        zeichen = chr(number % 256)
        number  = number / 256
        text.append(zeichen)
    
    return "".join(text)
    
        

'''
Created on 09.12.2009

@author: GWV7FD3
'''
import rsa

q   = 864006630282221617546607165505132768833442927403087253437971070579738052430368997434168187774249241951614756886898778257056066247808371060434399495780120519992351353974141025134838110883240469955211816819125032764542995315946722704756735945014229730497747034468419619537240011450094095310929293646545904289036986543253037388962051682151266850800780321722541
p   = 203760457035785707274440765779841571954960905020216438093288697556051306412361010381948211478739481724728871392770550387381532382660420658266741318271699868487291176814463322229620222245833529237754749958472949097604722412462711929816226562448624147196460229785274621791738101798102616023157685119198323119793328819060209462062125952867409315980899161557
n   = p * q
phi = (p - 1) * (q - 1)
e   = 1210475170735953725411

d   = rsa.findMultiplicativeInverse(p, q, e)

print d

#plain   = 123456789
#cipher  = rsa.modPow(plain, e, n)
#
#print cipher
#
#back    = rsa.modPow(cipher, d, n)
#
#print back

text    =   "Dieser Text soll in eine Zahl umgewandelt werden"
number  =   rsa.strToNumber(text)

print number
print rsa.numberToStr(number)

cipher  =   rsa.modPow(number, e, n)
cipher  =   rsa.numberToStr(cipher)

print cipher

cipher  =   rsa.strToNumber(cipher)
cipher  =   rsa.modPow(cipher, d, n)
plain   =   rsa.numberToStr(cipher)

print plain