TP3: Arithmétique et cryptographie

1. Arithmétique modulaire

  1. Construisez la table d'addition et de multiplication des entiers modulo 5. Pour une présentation plus agréable, considérez la fonction Matrix comme dans le TP 2
In [6]:
from sympy import *
import sympy as sy
In [7]:
x= sy.symbols('x')
y= sy.symbols('y')
add=sy.Lambda([x,y], (x+y)%5)
sy.Matrix(5,5,add) # pour l'addition
Out[7]:
Matrix([
[0, 1, 2, 3, 4],
[1, 2, 3, 4, 0],
[2, 3, 4, 0, 1],
[3, 4, 0, 1, 2],
[4, 0, 1, 2, 3]])
In [8]:
mult=sy.Lambda([x,y], (x*y)%5)
sy.Matrix(5,5,mult) # pour la multiplication
Out[8]:
Matrix([
[0, 0, 0, 0, 0],
[0, 1, 2, 3, 4],
[0, 2, 4, 1, 3],
[0, 3, 1, 4, 2],
[0, 4, 3, 2, 1]])
  1. Ecrivez une fonction CoprimeQ qui prend en entrée deux entiers et qui renvoie True si les entiers sont premiers entre eux
In [9]:
def CoprimeQ(n,m):
    return gcd(n,m)==1
In [10]:
CoprimeQ(3,11)
Out[10]:
True
  1. Programmez l'algorithme d'Euclide étendu itératif suivant et vérifiez qu'il fonctionne bien en comparant avec celui de la librairie Sympy. La fonction floor se trouve dans la librairie math mais corresond aussi à la division entière //. Les variables Q et R ne peuvent pas être des tuples (il n'y a pas d'arithmétique des tuples).
euclideEtendu(q,r) pour q
In [11]:
def euclideEtendu(q,r):
    if q>=r: raise Exception("q >= r")
    Q=sy.Matrix([1, 0])
    R=sy.Matrix([0, 1])
    while r !=0:
        t=q%r
        T=Q-(q//r)*R
        print(q,r,t,Q,(q//r),R,T)
        q,r = r,t
        Q,R=R,T
    return (Q,q)
In [12]:
euclideEtendu(11,26)

11 26 11 Matrix([[1], [0]]) 0 Matrix([[0], [1]]) Matrix([[1], [0]])
26 11 4 Matrix([[0], [1]]) 2 Matrix([[1], [0]]) Matrix([[-2], [1]])
11 4 3 Matrix([[1], [0]]) 2 Matrix([[-2], [1]]) Matrix([[5], [-2]])
4 3 1 Matrix([[-2], [1]]) 1 Matrix([[5], [-2]]) Matrix([[-7], [3]])
3 1 0 Matrix([[5], [-2]]) 3 Matrix([[-7], [3]]) Matrix([[26], [-11]])
Out[12]:
(Matrix([
 [-7],
 [ 3]]), 1)
In [13]:
gcdex(11,26)
Out[13]:
(-7, 3, 1)

Pour comprendre le fonctionnement, remplissez le tableau qui trace les valeurs de q,r,t,Q,floor(q/r),R,T.

  1. Ecrivez une fonction modinv qui prend en entrée a et m et qui renvoie l'inverse de amodulo m s'il existe et retourne une erreur sinon
In [14]:
def modinv(a,m):
    d=gcd(a,m)
    if d==1:
        return gcdex(a,m)[0]
    else:
        if d%b!=0: raise Exception("Pas d'inverse")
        else:
            return d*modinv(a/d, m/d)
In [15]:
modinv(3,26)
Out[15]:
9
  1. Reprenez le code de l'exponentielle modulaire $a^b\mod n$ et instrumentez le code pour faire la trace d'exécution en remplissant un tableau comme dans l'exemple
In [16]:
def exponentMod(a,b,p):
    res=1
    loop=0
    for i in bin(b)[2:]:
        res=(res*res)%p
        if i=='1':
            res=(res*a)%p
        print(loop,i,res**2, res)
        loop+=1
    return(res)

exponentMod(17,73,100)

0 1 289 17
1 0 7921 89
2 0 441 21
3 1 9409 97
4 0 81 9
5 0 6561 81
6 1 1369 37
Out[16]:
37

2. RSA

  1. Ecrivez une fonction genCle qui prend en entrée une taille (celle de la clé) exprimée en octets (1 octet = 8 bits) et qui retourne le tuple composé de l'entier $p$ et de l'entier $q$.
In [17]:
def genCle(o):
    o=o*4
    p=randprime(2**(o-1), 2**o)
    q=randprime(2**(o-1), 2**o)
    cle=(p,q)
    return(cle)
In [18]:
genCle(4)
Out[18]:
(62983, 33581)
  1. Ecrivez les fonctions clePub et clePriv qui ont un fonctionnement analogue à rsa_public_key et rsa_private_key. N'oubliez pas de fournir la valeur de e.
In [19]:
def clePub(p,q,e):
    return (p*q,e)

def clePriv(p,q,e):
    n=p*q
    phi=(p-1)*(q-1)
    d= modinv(e,phi)
    
    cle=(n,d)
    return cle
  1. Ecrivez une fonction RSAen Python qui prend en entrée :
    • soit la clé publique: le tuple $(n,e)$ et un entier $m$ et qui renvoie $m^e\mod n$
    • soit la clé privée: le tuple $(n,d)$ et un entier $c$ et qui renvoie $c^d\mod n$
In [28]:
def rsa(m,cle):
    return pow(m,cle[1],cle[0])
In [29]:
rsa(3,(509,11))
Out[29]:
15
  1. Utilisez votre fonction RSA pour construire RSAEnc et RDADec dont le comportement est analogue à encipher_rsa(m,pk) et decipher_rsa(c,dk) de l'implémentation RSA de Sympy.
In [22]:
def RSAEnc(m,pub):
    return rsa(m,pub)
In [23]:
RSAEnc(3,(509*521,11))
Out[23]:
177147
In [24]:
def RSADec(c,priv):
    return rsa(c,priv)
In [25]:
RSADec(177147,(509*521,216131))
Out[25]:
3
  1. En utilisant les fonctions de codage et de décodage du cours, tarnsformez les fonctions RSAEnc et RSADec pour qu'elles pemettent de chiffrer et de déchiffer des chaines de caractères.
In [26]:
DEFAULT_BLOCK_SIZE = 128 # taille bloc doit être inférieure à la taille de la clé et elle est en octets 
BYTE_SIZE=256 # un octet a 2**8=256 valeurs possibles


def Text2Ints(message,blockSize=DEFAULT_BLOCK_SIZE):
    # convertit une chaine en une liste de blocs d'entiers.    
    # chaque entier représente 'blockSize' caractères de la chaîne    
    messageBytes=message.encode('ascii')   
    # convertit la chaine en octets    
    blockInts=[]                           
    # initialise la liste de s entiers    
    for blockStart in range(0,len(messageBytes),blockSize):       
        # calculer l'entier correspondant au bloc de texte        
        blockInt=0        
        for i in range(blockStart,min(blockStart+blockSize,len(messageBytes))):            
            blockInt += int(messageBytes[i])*(BYTE_SIZE ** (i%blockSize))        
        blockInts.append(blockInt)    
    return blockInts


def Ints2Text(blockInts,messageLength,blockSize=DEFAULT_BLOCK_SIZE) :
    # convertit une liste de blocs d'entiers et retourne la chaine correspondante.    
    # on a besoin de la longueur du message passée dans messageLeng th pour convertir     
    # le dernier bloc d'entier    
    message=[]    
    for blockInt in blockInts:         
        blockMessage=[]         
        # initialise la liste qui contiendr a les caractères        
        for i in range(blockSize-1,-1,-1):            
            if len(message)+i < messageLength:                
                # décode la chaine des 'blockSize' caractères depui s ce bloc d'entier                
                charNumber=blockInt//(BYTE_SIZE**i)                
                # on passe au bloc suivant                
                blockInt=blockInt%(BYTE_SIZE**i)                
                blockMessage.insert(0,bytes([charNumber]).decode('a scii'))        
        message.extend(blockMessage)    
    return ''.join(message)
In [27]:
def RSAEncMessage(message,pub):
    m=Text2Ints(message)
    crypt=""
    for block in m:
        crypt=crypt+Ints2Text(RSAEnc(block,pub))
    return crypt

def RSADecMessage(crypt,priv):
    crypt=Text2Ints(message)
    message=""
    for block in crypt:
        message=message+Ints2Text(RSAEnc(block,priv))
    return message