KMOV Encryption

kmov.sage

from sage.all import *

def get_C2_prime():
    while True:
        p = random_prime(2^256-1,False,2^255)
        if p % 3 == 2:
            return p

        
### KEY GEN ###
e = 65537
p = get_C2_prime()
q = get_C2_prime()
assert (p % 3) == (q % 3) == 2
n = p*q
d = inverse_mod(e, (p+1)*(q+1))
assert e*d % ((p+1)*(q+1)) == 1
#d = inverse_mod(e, lcm((p+1),(q+1)))
#assert e*d % lcm((p+1),(q+1)) == 1
print "[+] p:", p
print "[+] q:", q
print


### Encryption ###
xm, ym = randint(1, n), randint(1, n)
b1 = (pow(ym, 2, n) - pow(xm, 3, n)) % n
En1 = EllipticCurve(Zmod(n), [0, b1])
#print "[+] En1 :", En1
Pm = En1(xm, ym)
print "[+] Pm :", Pm.xy()

Pc = e*Pm
print "[+] Pc = [e]Pm :", Pc.xy()

### Decryption ###
xc, yc = Pc.xy()
b2 = (pow(yc, 2, n) - pow(xc, 3, n)) % n
En2 = EllipticCurve(Zmod(n), [0, b2])
#print "[+] En2 :", En2

dec = d*Pc
print "[+] Dec = [d]Pc = [e*d]Pm :", dec.xy()

### Check ###
decX, decY = dec.xy()
print
print "[+] xm == decX, ym == decY ?", (xm == decX and ym == decY)


```
Result:
[+] p: 74865555229211703711715372449670288511233085374615721388786561214783290413777
[+] q: 88052263093162895553108351341437520707176786164653900106554771576925216906939

[+] Pm : (4942003061970302393176011614690326395997151515778807521631050137240145347315950422150253147761730701964678344406844978242539698733431789824007809025144708, 6344639808158816987383239921995793666114439972668732478033186852575828381838204447869548333992005149552573637608702902821166834943356605111884614221043886)
[+] Pc = [e]Pm : (4992985306737559047728678086015144434848453704186021736001188499488506359619675644651610988283020834512103395699740849294543000023140668360145104069331575, 5210535734355605799452073789869864768412269983859538757757249462386020728424451227587554595681919193070542313168534033212126509345975861387022830567138819)
[+] Dec = [d]Pc = [e*d]Pm : (4942003061970302393176011614690326395997151515778807521631050137240145347315950422150253147761730701964678344406844978242539698733431789824007809025144708, 6344639808158816987383239921995793666114439972668732478033186852575828381838204447869548333992005149552573637608702902821166834943356605111884614221043886)

[+] xm == decX, ym == decY ? True
```