︠cce67f71-8797-4df6-af1d-78660fb66c43i︠
%latex
\flushleft \emph{El Gamal Encryption}:\\
\subsection{Encryption}
\begin{enumerate}
    \item Select randomly a number $r < P-1$ such that $gcd(r, P-1) = 1$.
    \item Compute $y_1 = g^r \mod P$.
    \item Compute $y_2 = M * b^r \mod P$
    \item Ciphertext is $(y_1, y_2)$
\end{enumerate}
\subsection{Decryption}
\begin{enumerate}
    \item Compute $D = y_2 * (y_1)^{-x} \mod P$
\end{enumerate}

︡1f9d26f7-3b22-43db-ae45-d93f36ea4bb8︡{"file":{"filename":"/tmp/tmpheTIQf.png","show":true,"text":null,"uuid":"cc0f8cd2-7622-4176-9c5b-029d611926bd"},"once":false}︡{"done":true}︡
︠d36f3160-8e22-40dc-89ff-4a7cd01a24b1s︠

import random

# key generation
# public key (g,b,p)
# secret key (x)
p = next_prime(451643)
x = random.randint(1, p)
g = random_prime(p)
b = power_mod(g,x,p)

# encryption
m = 12345
r = random.randint(1, p-1)
while gcd(r,p-1) != 1:
    r = r +1
    if r >= p-1:
        r = random.randint(1, p-1)
y1 = power_mod(g,r,p)
y2 = mod((m * power(b,r)), p)

#decryption
d = mod(y2 / power(y1, x), p)

print("orginal message is %d, decrypted message is %d" %(m, d) )
︡b9fb0d89-4f20-420e-9e26-563ab6f7c985︡{"stdout":"orginal message is 12345, decrypted message is 12345\n"}︡{"done":true}︡











Collaborative Calculation and Data Science

colby

sagemath

cornellcollege

facebook