3806.sagews

MESSAGE IMPORTANT : Avant tout, il faut faire Action->Evaluate All afin que les fonctions antécédentes soient reconnues par les fonctions ultérieures. J'ai tout testé plusieurs fois et ça devrait fonctionner chez vous aussi ^^ Bonne lecture ;)

QUESTION 1 : La fonction suivante est destinée à décomposer un nombre n-1 (on donne d'abord l'impair potentiellement premier n, auquel on retranche 1 afin de procéder au test de primalité) en produit de 2**s et d. n-1 est donc pair si on suppose n premier.

def decomposition(n):
    s=0
    d=n-1
    while d%2==0:
        d=d/2
        s+=1
    return (d,s)

Je définis ci-dessous une fonction permettant de calculer a**d[n], répondant au doux nom de ExpoModulo ^^

def ExpoModulo(a,d,n):
    b=a%n
    if d==0:
        return 1
    if d==1:
        return a%n
    while d>1:
        b=b*a%n
        d-=1
    return b

Voilà enfin le fameux test (enfin le mien) de primalité de Miller Rabin : Tout d'abord, un nombre a est choisi aléatoirement entre 1 et n-1, afin de satisfaire les conditions du théorème de Fermat. On pose ensuite n-1 = d*2**s grâce à decomposition(n), puis on étudie les valeurs (modulo n) de c = a**d Si a**(n-1)=1[n], alors n a de fortes chances d'être premier : c'est le cas lorsque c*b = (a**d)*(a**2**s) = a**(n-1) = 1[n]

def MillerRabin(n):
    a=randint(2,n-1)
    
    if n%2==0 :
        return False
    #bien entendu, si un nombre est pair, alors il n'est pas premier !
    
    (d,s)=decomposition(n)
    #donc n-1 sera decompose en d*2**s
     
    b=ExpoModulo(a,2**s,n)
    c=ExpoModulo(a,n-1,n)
    
    if c!=1:
        return False
    #on cherche a**(n-1)%n (theoreme de Fermat), avant toute chose, c'est different de 1 (mod n), n n'est pas premier
    
    TEST1=False

    for r in range (s):
        b=ExpoModulo(a,2**r,n)
        if b!=1:
            TEST1=True
        #si parmi les racines carrees on a un nombre different de 1, alors on est sur la voie de la primalite

    if TEST1:
        e=ExpoModulo(a,2**(s-1),n)
        if e%n==n-1:
            return True
        #si l'avant derniere racine est congrue a n-1 (donc -1[n]), alors on a bien un nombre premier

    return False

La fonction suivante définit des statistiques, qui sont avant tout le principe de base du test de Miller Rabin : On entre le nombre de tests à effectuer, puis le nombre dont on désire tester la primalité. La sortie est le nombre d'itérations (utile pour la fonction suivante), les résultats positifs et négatifs.

def stats(k,n):
    f=0
    v=0
    for i in range(k):
        if MillerRabin(n):
            v+=1
        else:
            f+=1
    #print "Sur ", k, "essais, le test montre ", v, "resultat(s) de primalite positif(s) et ", f, "negatif(s)"
    return (k,v,f)

Enfin vient la fonction qui permet de donner un résultat de primalité, si le nombre de tests est supérieur à 100. En dessous, c'est trop peu précis pour être fiable.

def Resultat(k,n):
    k,a,b=stats(k,n)
    if k>=100:
        return (a != 0)
    else:
        return "Le nombre de tests est trop faible pour etablir une statistique fiable, donnez au moins 100 iterations"

QUESTION 2 : Voilà ma fonction Prem(i). Elle renvoie le premier nombre n tiré au hasard entre 10**(i-1) et 10**i-1 dont la primalité est vérifiée par mon test Miller Rabin, mais aussi les statistiques sur 100 essais.

def Prem(i):
    if i==0:
        return "i doit etre superieur a 1"
    elif i==1:
        a=3
        b=9
    else:
        a=10**(i-1)
        b=10**i-1
    for k in range(a,b):
        n=randint(a,b)
        if Resultat(100,n):
            return n
            
Prem(5)

18913

QUESTION 3: La fonction récursive pgcd(a,b), qui fonctionne aussi comme pgcd(b,a), rapide d'exécution.

def pgcd(a,b):
    if a<b:
        return(pgcd(b,a))
    if a%b==0:
        return b
    return(pgcd(b,a%b))

Arrive donc la fonction PremierAvec(a,n), réponse à la question 3, qui utilise la fonction pgcd(a,b) précédemment écrite.

def PremierAvec(a,n):
    for k in range(2,1000):
        n=randint(2,n)
        if pgcd(a,n)==1:
            return n

QUESTION 4 : Un élément dans Z/nZ est dit inversible (mod n) s'il admet un autre élément de Z/nZ tel que le produit des deux est congru à 1 (mod n). La fonction Inverse(a,n) cherche donc un inverse à a, dans Z/nZ

def Inverse(a,n):
    for b in range(1,n):
        if (a*b)%n==1:
            return b
    return None

QUESTIONS 5 & 6 : Le codage RSA : On choisit d'abord deux nombres p et q supposés premiers, et pour la suite, les notes dans la fonction parlent d'elles mêmes.

def CleInit(i):
    p,q=Prem(i),Prem(i)
    #p et q sont deux grands nombres supposés premiers
    
    n=p*q
    #on va trouver n = p*q, puis en calculer l'indicatrice d'Euler phi=f=(p-1)*(q-1).
    f=(p-1)*(q-1)
    
    #ensuite, cherchons d tel que pgcd(f,d)=1.
    d=PremierAvec(f,n)

    #enfin, trouvons e tel que ed=1[f], donc e est l'inverse de d (mod f).
    e=Inverse(d,f)

    #c (publique) est le couple (e,n), et c' (privée) est le couple (d,f)
    return ((e,n),(d,f))

def Chiffrement(m,(e,n)):
    mc=m**e
    mc=mc%n
    return mc
    
def Dechiffrement(mc,(e,n),(d,f)):
    return ExpoModulo(mc,d,n)

(cpb,cpv)=CleInit(3)
print "clef publique ", cpb, "clef privee", cpv
mc=Chiffrement(6543,cpb)
print "message a coder ", "message code", mc
md=Dechiffrement(mc,cpb,cpv)
print "message decode", md

clef publique (32447, 70437) clef privee (60891, 69836) message a coder message code 59190 message decode 6543

QUESTION 7 : Je définis tout d'abord les fonctions permettant de calculer le modulo (car sage craint la division de zéro ^^'), puis les fonctions de conversion de binaire à décimal, et vice et versa, et enfin la conversion de chaine de caractère en binaire, et l'inverse.

def modulo(a,n):
    a=int(a)
    n=int(n)
    while a>=n:
        a-=n
    return a
modulo(28,2)

0

def inverse_c(c):
    k=len(c)
    d=''
    for i in range(k):
        d+=c[k-i-1]
    return d 

inverse_c('Julien')

'neiluJ'

def binaire(n):
    bin=''
    a=n
    while a>=1:
        b=modulo(a,2)
        #print a,b
        a=a/2
        bin+=str(b)
    while len(bin)<7:
        bin+='0'
        #en effet, comme on bosse sur du ASCII et qu'il faut que les caractères soient en général codés par 7 bits,
        #je rajoute des 0 afin de combler le trou qui ferait tout bugger dans le cas d'un caractère c dont ord(c)<=32.
    return(inverse_c(bin))

def decimal(c):
    c=str(c)
    n=0
    k=len(c)
    for i in range(k):
        a=int(c[i])
        n+=a*2**(k-i-1)
    return n

def MessageBinaire(m):
    k=len(m)
    mbin=''
    for i in range(k):
        carbin=''
        v=ord(m[i])
        carbin=binaire(v)
        mbin+=carbin
    return mbin

#codé sur 7 bits ! ! !

def BinaireMessage(b):
    k=len(b)
    mes=''
    if k%7!=0:
        return "Erreur de taille "
    for i in range(0,k,7):
        lettre=''
        for j in range(0,7):
            lettre+=b[i+j]
        lettre=int(lettre)
        v=decimal(lettre)
        carmes=chr(v)
        mes+=carmes
    return mes

Enfin nous pouvons créer les fonctions Encodage et Décodage, très facilement à l'aide des fonctions usuelles précédentes. Et ça marche à la perfection !

def Encodage(s):
    return(decimal(MessageBinaire(s)))

def Decodage(n):
    return(BinaireMessage(binaire(n)))

# PS : Si vous avez la foi d'attendre le résultat, décodez donc ceci :
    	

# 1351413578771936095962770007

# ;)

def RSA(s,i):
    (e,n),(d,f)=CleInit(i)
    print "codes", (e,n),(d,f)
    m=Encodage(s)
    print "message", m
    print "re codes", (e,n),(d,f)
    mc=Chiffrement(m,(e,n))
    print "message code", mc
    print "encore les codes", (e,n),(d,f)
    a=Dechiffrement(mc,(e,n),(d,f))
    print "message dechiffre", a
    print "les codes une ultime fois", (e,n),(d,f)
    return Decodage(a)