#!/usr/bin/env python
'''
#!/usr/local/bin/python 
from sys import*;from string import*;a=argv;[s,p,q]=filter(lambda x:x[:1]!=
'-',a);d='-d'in a;e,n=atol(p,16),atol(q,16);l=(len(q)+1)/2;o,inb=l-d,l-1+d
while s:s=stdin.read(inb);s and map(stdout.write,map(lambda i,b=pow(reduce(
lambda x,y:(x<<8L)+y,map(ord,s)),e,n):chr(b>>8*i&255),range(o-1,-1,-1)))

from http://www.amk.ca/python/writing/crypto-curiosa
without padding
'''
from sys    import *
from string import *
from random import randrange
from math   import log
def rsa(m, p, q, d):
    e, n = atol(p,16), atol(q,16)   # pubkey
    l = (len(q) + 1) / 2            # is this same with k?
    o, inb = l - d, l - 1 + d       # inb is ignored for correct value, why?
    if not d:
        k = int(log(n) / log(2) / 8 + 1)# k as described in RFC 2313
        m = '\x00\x02' + random_bytes(k - len(m) - 3) + '\x00' + m  # padding
    ret, s = [], True               # init ret and while loop
    while s:
        s = m                       # s = m[:inb]
        m = None                    # m = m[inb:]
        s and map(ret.extend,
                  map(lambda i,b=pow(reduce(lambda x,y:(x<<8L)+y,map(ord,s)),e,n):chr(b>>8*i&255),
                      range(o-1,-1,-1)
                     )
                 )
    ret = ''.join(ret)
    if d:
        return ret[ret.index('\x00', 2) + 1:]
    else:
        return ret

def random_bytes(size):
    size = max(8, size)
    return ''.join(chr(randrange(1, 256)) for i in xrange(size))    # non-zero

def test(m = 'Hello World!'):    
    # e, n, p, q generated by python-rsa from http://stuvel.eu/rsa
    e = '10001'
    n = '483843201aaecd6a67ee700d017294e30372ce0c4f73c505ea1409367cc33d4517cb2b118da9a8242453a90e40db83b6cd011fbe19309781a5b0522dbd043959'
    # d calculated using e, p, q by codes from http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Practical_Implementation_in_Python
    d = '3edbc9811df85b8e6bdb9ae79704f616092059bb5944388e8748dd23f1beec180a44f1fdff67c08670b27e0253e1460c4651d685421e6007af37f1c4118a64a1'
    print 'message: %s\n' % m
    ed = rsa(m, e, n, False)
    print 'encoded: %s\n' % ed
    dd = rsa(ed, d, n, True)
    print 'decoded: %s\n' % dd
    print 'Correct!' if dd == m else 'Oops...'

if __name__ == "__main__":
    if len(argv) > 1:
        test(argv[1])
    else:
        test()
