公開鍵PK と平文Mの入力に対し，128 ビット乱数K を生成し，OAEP で鍵K にパディングを付加し，RSA暗号を用いてK を暗号化し，同時にK を用いてRC4 で平文M を暗号化する関数

HybridEnc.py

# Maeda Keiichi

import os, binascii, hashlib, base64, struct, pickle

def long_to_bytes(n, blocksize=0):
  s = ''
  n = long(n)
	pack = struct.pack
	while n > 0:
		s = pack('>I', n & 0xffffffffL) + s
		n = n >> 32
	for i in range(len(s)):
		if s[i] != '\000'[0]:
			break
	else:
		s = '\000'
		i = 0
	s = s[i:]
	if blocksize > 0 and len(s) % blocksize:
		s = (blocksize - len(s) % blocksize) * '\000' + s
	return s

def ceil_div(a, b):
	if not isinstance(a, (int, long)) or not isinstance(b, (int, long)):
		raise TypeError("unsupported operand type(s): %r and %r" % (type(a).__name__, type(b).__name__))
	(q, r) = divmod(a, b)
	if r:
		return q + 1
	else:
		return q

def MGF1(mgfSeed, maskLen):
	T = ""
	for counter in xrange(ceil_div(maskLen, hashlib.sha1().digest_size)):
		c = long_to_bytes(counter, 4)
		T = T + hashlib.sha1(mgfSeed + c).digest()
	return T[:maskLen]

    
def exeuclid(a, b):
    a0, a1 = a, b
    x0, x1 = 1, 0
    y0, y1 = 0, 1
    while(1):
        if a1 == 0:
            return x0, y0
        q1 = int(a0 / a1)
        a2 = a0 % a1
        x2 = x0 - q1 * x1
        y2 = y0 - q1 * y1
        a0, a1 = a1, a2
        x0, x1 = x1, x2
        y0, y1 = y1, y2

def modBinary(g, k, p):
    if k == 0:
        return 1
    y = g
    kb = format(k, 'b')
    for i in xrange(1,len(kb)):
        if kb[i] == '1':
            y = mod(pow(y, 2, p) * g, p)
        else:
            y = pow(y, 2, p)
    return(y)

def modCRTBinary(g, r, p, q, x, y):
    n = p * q
    r1 = mod(r, p-1)
    r2 = mod(r, q-1)
    g1 = mod(g, p)
    g2 = mod(g, q) 
    a = modBinary(g1, r1, p)
    b = modBinary(g2, r2, q)
    s1 = p * x
    s2 = q * y   
    return mod(s2 * a + s1 * b, n)

def RSAEnc(m, n, e):
    return modBinary(m, e, n)

def RSADec(c, d, p, q, x, y):
    return modCRTBinary(c, d, p, q, x, y)

def int2bin(i):
    i_tmp = "%x" % i
    if (len(i_tmp) % 2 == 0):
        return binascii.unhexlify(i_tmp)
    else:
        return binascii.unhexlify("0" + i_tmp)

def bin2int(b):
    return int(binascii.hexlify(b),16)

def RSAOAEPEnc(m, n, e, r, k0, k1, k2):
    s = bin2int(MGF1(int2bin(r),k-k0-1)) ^ bin2int(int2bin(ONE_HASH) + ('0' * k1) + '1' + int2bin(m))
    t = bin2int(MGF1(int2bin(s),k0)) ^ r
    w = bin2int('0' + int2bin(t) + int2bin(s))
    return RSAEnc(w,n,e)

def RSAOAEPDec(cipher,d,p,q,x,y):
    w_str = int2bin(RSADec(cipher,d,p,q,x,y))
    t_str = w_str[1:k0+1]
    s_str = w_str[k0+1:]
    r = bin2int(t_str) ^ bin2int(MGF1(s_str,k0))  
    m_etc_str = int2bin(bin2int(s_str) ^ bin2int(MGF1(int2bin(r),k-k0-1)))
    PS = m_etc_str[20:20+k1]
    if (PS == ('0' * k1)):
        m = bin2int(m_etc_str[20+k1+1:]) 
        return (m,True)
    else:
        return ("No",False)
    
def KSA(S,K_str):
    K = []
    for a,b in zip(K_str[0::2],K_str[1::2]):
        K.append(int('%s%s' % (a,b),16))
    n = size(S)
    j =0
    for i in range(n):
        j = (j + S[i] + K[i % len(K)]) % n
        S[i],S[j] = S[j],S[i]
    return S

def PRGA(S, len):
    n = size(S)
    Keystream=[]
    i = 0
    j = 0
    for i in range(len):
        i = (i + 1) % n
        j = (j + S[i]) % n
        S[i],S[j] = S[j],S[i]
        Keystream.append( S[ (S[i]+S[j]) % n] )
    return Keystream

def RC4Enc(m,z):
    cipher=""
    for i,j in zip(m,z):
        cipher+=(chr(ord(i) ^ j))
    return cipher


def HybridEnc(K, m, n, e, r, k0, k1, k2):
    Ck = RSAOAEPEnc(K,n,e,r,k0,k1,k2)
    S = [i for i in range(256)]
    S = KSA(S,"%x" % K)
    length = len(m)
    z = PRGA(S,length) 
    Cm = RC4Enc(m,z)
    return Ck,Cm

def HybridDec(Ck , Cm , d, p, q, x, y):
    K,ok = RSAOAEPDec(Ck,d,p,q,x,y)
    if not(ok):
        return false
    S = [i for i in range(256)]
    S = KSA(S,"%x" % K)
    length = len(Cm)
    z = PRGA(S,length) 
    m = RC4Enc(Cm,z)
    return K,m


ONE_HASH = 1245845410931227995499360226027473197403882391305

k0 = 20
k1 = 70
k2 = 16
k = 2*k0 + k1 + k2 + 2

p2 = 11853085763133505990286201269363921131755361282207771806454216823906463045956110404018518118871988561332197770015175458025096566875663947404231597048649687
q2 = 13241479879786700069537673013402283713461303895018638725043715728333351182535991791698730454905679569343041660910401104499998964541968688709360528771269943
n2 = 156952396645918502955193834718776388506857399213019211056913567025447783623953424981098100320371797037390713527200065108048504302347881505742461209041764469658052100493063095556772159136964337847882433273567579158528625301415253145239724411443393127148129610564195773940563184444586953330741471865748319457841
e1 = 16906953396398285955
d1 = 724312013274593559104718233668131011194996096397911006981852189172961239048948863282836141926358773822231408712979119342947633487509489681999208855556699754187911367602954918028434935166295469845715934583725830138105140714265139027719788715269467483599026617823666098202900871395864967128743435198316095145
r4 = 1316477832003765415247735379263525718150288987267
x2,y2 = exeuclid(p2, q2)

M = "Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing."

K = bin2int(os.urandom(16))

Ck,Cm = HybridEnc(K, M, n2, e1, r4, k0, k1, k2)

f = open('HybridEnc.out', 'wb')
pickle.dump(base64.b64encode(int2bin(Ck)), f)
pickle.dump(base64.b64encode(Cm), f)
f.close()

f = open('HybridEnc.out', 'rb')
Ck = bin2int(base64.b64decode(pickle.load(f)))
Cm = base64.b64decode(pickle.load(f))
f.close()

K, M = HybridDec(Ck , Cm , d1, p2, q2, x2, y2)

print "K =",K
print "m =",M