#!/usr/bin/env python
# coding: utf-8

# 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_)


# # Resources

# - https://www.agwa.name/blog/post/duplicate_signature_key_selection_attack_in_lets_encrypt
# - https://crypto.stackexchange.com/questions/47445/rsa-duplicate-signature-attack
# - https://mailarchive.ietf.org/arch/msg/acme/F71iz6qq1o_QPVhJCV4dqWf-4Yc/

# In[ ]: