In [4]:

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD
from Crypto.Hash.SHA256 import SHA256Hash
import random

In [9]:

def key_creation():
    p = getPrime(128)
    q = getPrime(128)
    N = p * q
    while True:
        e = random.randint(N//4,N-1)
        if(GCD(e, (p-1)*(q-1)) == 1):
            break
    return (p, q), (N, e)

def rsa_ds_sign(D, p, q, N):
    D = bytes_to_long(D)
    d = inverse(e, (p-1)*(q-1)) #compute private key
    S = pow(D, d, N) #compute signature
    return long_to_bytes(S)

def rsa_ds_verif(D, S, e, N):
    D = bytes_to_long(D)
    S = bytes_to_long(S)
    return pow(S, e, N) == D #verify using public key

Prerequisites¶

RSA signatures
Modular arithmetic

Theory¶

Let $(G, E, D)$ be our signing algorithm based on RSA

$p, q$ primes
$N = pq;\ \varphi(N) = (p-1)(q-1)$
$d \equiv e^{-1} \bmod \varphi(N)$

RSADSA

Sign: $\sigma = m^d \bmod N$
Verify: $m == \sigma^e \bmod N$

Task

Given a signature $\sigma$ an attacker can choose a new message $m'$ and a $k_{pub} =(N', e')$ such that $m' == \sigma^{e'} \bmod N'$

The attacker can choose can choose $e = 1$

We know

$s \equiv m' \bmod (s - m') \iff s - (s - m') \equiv m' \bmod (s - m') \iff m' \equiv m' \bmod (s - m')$
Therefore the attacker sends $(N', e') = (s-m', 1)$

Code¶

In [5]:

(p, q), (N, e) = key_creation()

In [10]:

m = b'secret_message'
s = rsa_ds_sign(m, p, q, N)

In [12]:

#compute our public key
N_ = bytes_to_long(s) - bytes_to_long(m)
e_ = 1

In [14]:

#verif
rsa_ds_verif(m, s, e_, N_)

Out[14]:

True

Resources¶

In [ ]: