Simple RSA implementation in Python

rsa.py

#! /usr/bin/python

#
# Copyright (C) 2014 Bilal Akhtar <me@itsbilal.com
#
# Licensed under the MIT license.
#

from fractions import gcd

def phi(a,b):
	return (a-1)*(b-1)

def coprime(n):
	# Find largest coprime to n and return it
	j=1
	for i in range(2,(n-1)):
		if gcd(n,i) == 1: # Coprime
			j = i

	return j

def isprime(n):
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        return False
    # 2 is the only even prime number
    if n == 2: 
        return True    
    # all other even numbers are not primes
    if not n & 1: 
        return False
    # range starts with 3 and only needs to go up the squareroot of n
    # for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

def encrypt(n, e):
	ci = int(raw_input("Enter unicode character to be encrypted:"))
	print "c = %i" % pow(ci, e, n)


def decrypt(n, d, c):
	print "Decrypting c ..."

	print "Result: m = %i" % pow(c, d, n)

def keygen(primes):
	# We should output n and e, and keep pq and d secret.
	p,q = primes
	n = p*q
	e = coprime(phi(p,q))

	d = 1
	# Calculating d
	for d in range(3,phi(p,q)):
		if (d*e) % phi(p,q) == 1:
			break

	# Output
	print "Give these values to the sender: \n e = %i \nn = %i \n\n" % (e,n)
	print "And store these values for future reference:"
	print "d = %i \np = %i \nq = %i \n" % (d,primes[0],primes[1])

def crack(n,e):
	# First, find all prime numbers that multiply to give n
	# For each p,q possibility, check if phi(p,q) and e are coprime
	for i in range(2,n-1):
		if isprime(i) and (n % i) == 0:
			j = n/i
			if isprime(j):
				# Match found, check for coprime
				if gcd(e, phi(i,j)) == 1:
					print "Match found: %i, %i" % (i,j)
					return

	print "No match found"

if __name__ == "__main__":
	print "Welcome to RsaPy"

	b = raw_input("Type e for encrypting, d for decrypting, g for keygen: ")

	if b == 'd':
		n = int(raw_input("n = "))
		d = int(raw_input("d = "))
		c = int(raw_input("c = "))

		decrypt(n, d, c)
	elif b == 'e':
		n = int(raw_input("n = "))
		e = int(raw_input("e = "))
		encrypt(n,e)
	elif b == 'g':
		i = tuple(int(x.strip()) for x in raw_input("Enter p,q (any two prime numbers): ").split(','))
		keygen(i)
	elif b == "1337":
		print "\n\nYou may pass, my lord.\n\n"

		n = int(raw_input("n = "))
		e = int(raw_input("e = "))
		crack(n,e)