automatic_names(True)

# conversion d'une phrase en minuscule en liste de nombres correspondant aux lettres

def string2numlist ( phrase ) :
    
    numlist = []
    
    for pos in range(0, len(phrase)) :
        if ord(phrase[pos]) in range (97, 123) :                ## on est bien en minuscule
            numlist.append( ord(phrase[pos]) - 96)              ## et on enlève 96 pour que a->1, b->2, etc.
        else :                                                  ## sinon (espace ou pas minuscule ou autre)
            numlist.append( 0 )                                 ## on met un 0
    return (numlist)




# meme chose avec virgules, points et apostrophes
def string2numlist_ext ( phrase ) :
    
    numlist = []
    
    for pos in range(0, len(phrase)) :
        if ord(phrase[pos]) in range (97, 123) :
            numlist.append( ord(phrase[pos]) - 96)
        elif phrase[pos] == ',' :
            numlist.append( -1 )
        elif phrase[pos] == '.' :
            numlist.append( -2 )
        elif phrase[pos] == "'" :
            numlist.append( -3 )
        else :
            numlist.append(0)
    return (numlist)




# conversion d'une liste de nombres en phrase de lettres minuscules
def numlist2string ( numlist ) :
    
    phrase = ''
    
    for pos in range(0, len(numlist)) :
        if numlist[pos] in range(1,27) :                          ## si on est entre 1 et 26
            phrase = phrase + chr(numlist[pos] + 96)              ## on concatène la lettre correspondante
        else :                                                    ## sinon
            phrase = phrase + chr(32)                             ## on met un espace
    return (phrase)



## conversion d'une liste de nombres en phrase de lettres minuscules avec apostrophes, points, virgules
def numlist2string_ext ( numlist ) :
    
    phrase = ''

    for pos in range(0, len(numlist)) :
        if numlist[pos] in range(1,27) :
            phrase = phrase + chr(numlist[pos] + 96)
        elif numlist[pos] == -1 :
            phrase = phrase + ','
        elif numlist[pos] == -2 :
            phrase = phrase + '.'
        elif numlist[pos] == -3 :
            phrase = phrase + "'"
        else :
            phrase = phrase + chr(32)
    return (phrase)




## chiffrement par décalage
def chiffre_decalage (message, decalage) :
    mess_numlist = string2numlist (message)
    crypt_numlist = []
    for i in range(len(mess_numlist)) :
        if mess_numlist[i] <> 0:
            crypt_numlist.append((mess_numlist[i] + decalage - 1)%26 + 1)
        else :
            crypt_numlist.append(0)
    return numlist2string(crypt_numlist)




## chiffrement permutations
def chiffre_permutation (message, permutation ) :
    mess_numlist = string2numlist (message)
    perm_numlist = string2numlist (permutation)
    
    crypt_numlist = []
    
    for pos in range(len(mess_numlist)) :
        if mess_numlist[pos] <> 0 :
            crypt_numlist.append( perm_numlist[mess_numlist[pos] - 1] )
        else :
            crypt_numlist.append(0)
    return numlist2string(crypt_numlist) 




## déchiffrement permutations
def dechiffre_permutation (message, permutation ) :
    mess_numlist = string2numlist (message)
    perm_numlist = string2numlist (permutation)

    perm_numlist_inv = [perm_numlist.index(i)+1 for i in range(1,27)]
    permutation_inverse = numlist2string (perm_numlist_inv)    

    return chiffre_permutation(message, permutation_inverse)




## chiffrement de Polybe
def chiffre_polybe (message) :
    polybe = [str(i+1) +  str(j+1) for i in range(5) for j in range(5)]
    mess_numlist = string2numlist(message)
    result = ''
    for i in range(len(mess_numlist)) :
        if mess_numlist[i] == 10 :
            result = result + polybe[8]
        elif mess_numlist[i] == 0 :
            result = result + ' '
        elif mess_numlist[i] < 10 :
            result = result + polybe[mess_numlist[i]-1]
        elif mess_numlist[i] > 10 :
            result = result + polybe[mess_numlist[i]-2]
    return result


## dechiffrement polybe
def dechiffre_polybe (message) :
    polybe = [str(i+1) +  str(j+1) for i in range(5) for j in range(5)]

    current = ''
    decrypt = []
    i = 0
    while i < len(message):
        if message[i] <> ' ' :
            current = message[i] + message[i+1]
            i = i+2
            if ZZ(current) <= 24 :
                decrypt.append(polybe.index(current)+1)
            else :
                decrypt.append(polybe.index(current)+2)
        else :
            decrypt.append(0)
            i = i + 1
            
    return numlist2string(decrypt)







## chiffrement de Vigenere
def chiffrement ( message, cle ) :

    chiffre_numlist = []
    
    # on calcule les listes de nombres correspondant au message et a la cle
    mess_numlist = string2numlist (message)
    cle = string2numlist (cle)
    
    # ensuite on ajoute les nombres du message à ceux de la clé, en répétant ceux de la clé,
    # tout ca modulo 27 (26 + 1 pour l'espace) 
    for pos in range(0, len (mess_numlist)) :
         chiffre_numlist.append( (mess_numlist[pos] + cle[pos%len(cle)])%27 ) # a%b c'est le representant dans [0,b] de a mod b
    
    return(numlist2string(chiffre_numlist))


## déchiffrement de Vigenere
def dechiffrement ( message, cle ) :

    dechiffre_numlist = []
    
    # on calcule les listes de nombres correspondant au message et a la cle
    mess_numlist = string2numlist (message)
    cle = string2numlist (cle)
    
    # ensuite on ajoute les nombres du message à ceux de la clé, en répétant ceux de la clé,
    # tout ca modulo 27 (26 + 1 pour l'espace) 
    for pos in range(0, len (mess_numlist)) :
         dechiffre_numlist.append( (mess_numlist[pos] - cle[pos%len(cle)])%27 )
    
    return(numlist2string(dechiffre_numlist))




###############################
#### courbes elliptiques   ####
###############################
def courbe_elliptique (courbe, verbose = false) :

    a = courbe[0]
    b = courbe[1]
        
    if verbose :
        print 'y^2 = x^3 +',a,'x +',b
    
    if 4*a^3 + 27*b^2 <> 0 :
        if verbose :
            print 'est une courbe elliptique'
        return true
    else :
        if verbose :
            print 'n\'est pas une courbe elliptique'
        return false


def est_sur_la_courbe ( P, courbe) :

    if P == [infini,infini] :
        return True

    a = courbe[0]
    b = courbe[1]
    xP = P[0]
    yP = P[1]

    if yP^2 - xP^3 - a*xP - b == 0 :
        return True
    else :
        return False




def somme (P, Q, courbe) :     # P et Q sont des listes de deux coordonnées,
                               # éventuellement [infini, infini] pour le point à l'infini

    # d'abord on regarde si P et Q sont sur la courbe
    if est_sur_la_courbe(P, courbe) == False or est_sur_la_courbe(Q, courbe) == False :
        raise ValueError('Tous les points ne sont pas sur la courbe')

    # si un des points est le point à l'infini
    if P == [infini, infini] :
        return Q

    if Q == [infini, infini] :
        return P
        

    # sinon pour que le code soit clair, on donne des petits noms aux coordonnées
    xP = P[0]
    yP = P[1]
    xQ = Q[0]
    yQ = Q[1]

    
    # cas trivial ou on renvoit le point à l'infini    
    if xP == xQ and yP == - yQ :
        return [infini, infini]


    # cas sympa où P et Q sont distincts
    if xP <> xQ :
        pente = (yP - yQ )/(xP - xQ)
        xR = pente^2 - xP - xQ
        yR = - (yP + pente*(xR - xP))
        return [xR, yR]
        

    # cas où P = Q avec yP = yQ <> 0
    # normalement c'est le seul cas restant
    if P == Q and yP <> 0 :
        pente = (3*xP^2 + courbe[0]) / (2*yP)
        xR = pente^2 - 2*xP
        yR = -(yP + pente*(xR - xP))
        return [xR,yR]



def multiple_naif (k, P, courbe) :
    
    if k == 1 :
        return P
    
    mult = P
    for i in range(1,k) :  # range(1,k)=[1,...,k-1] donc avec le mult = P au dessus
                           # on a bien P +...+P k fois
        mult = somme(mult,P, courbe)
    return(mult)





def multiple (k, P, courbe) :
    if k == 0 :
        return [infini,infini]
    if k == 1 :
        return P
    elif k%2 == 0 :
        return multiple (k/2, somme(P, P, courbe), courbe)
    elif k%2 == 1 :
        return somme (P,multiple ((k-1)/2, somme(P, P, courbe), courbe), courbe)



def trouve_point(courbe, p) :    

    K = GF(p)
    # si p <> 3 mod 4, c'est plus compliqué
    if p%4 == 1 :
        raise ValueError('p n\'est pas congru à 3 modulo 4')
        
    a = courbe[0]
    b = courbe[1]    
    
    # on prend un x random, on calcule x^3 + ax +b et si c'est un carré on en prend une racine
    # pour savoir si c'est un carré, on calcule le symbole de Legendre, i.e. (.)^((p-1)/2)
    
    pas_carre = True
    while pas_carre :
        xP = K.random_element()
        yPcarre = xP^3 + a*xP + b
        if yPcarre^((p-1)/2) == K(1):
            pas_carre = False  # c'est un carre donc pas_carre est faux...
        else :
            pas_carre = True

    
    # à la sortie de la boucle, yPcarre = x^3 + ax + b est un carré, donc on en prend la racine
    # en calculant (.) ^ ((p+1)/4)
    
    yP = (yPcarre)^((p+1)/4)

    return [xP, yP]


def numlist2string ( numlist ) :
    
    phrase = ''
    
    for pos in range(0, len(numlist)) :
        if numlist[pos] in range(1,27) :                          ## si on est entre 1 et 26
            phrase = phrase + chr(numlist[pos] + 96)              ## on concatène la lettre correspondante
        else :                                                    ## sinon
            phrase = phrase + chr(32)                             ## on met un espace
    return (phrase)

####
### OLD BRUTEFORCE
####
# borne = ceil(RR(K.characteristic() + 1 + 2*sqrt(p))) 
def bruteforce_DH (courbe, P, aP, bP, borne) : # pour la borne on prend le
                                                                              # pire que donne le thm de Hasse

    mult_P = P
    for i in IntegerRange(1,borne) :     # on va de 1 à p-1. Il faut mettre IntegerRange et pas range
                                         # pour avoir les grands nombres (sinon erreur)
        
        if i%50 == 0 :
            print('.')
        mult_P = somme (P, mult_P, courbe)
        
        if mult_P == aP :
            print 'on a trouvé \'a\' !'
            return i+1   # +1 à cause du décalage dans range()
        if mult_P == bP :
            print 'on a trouvé \'b\' !'
            return i+1
    print 'borne atteinte, on n\'a rien trouvé '
    return 0

####
### les blackboxes
####
def genere_premier () :
    n = 9**ZZ.random_element(25,30)*8**ZZ.random_element(10,15)
    p = next_prime (n)
    while p%4 != 3 :
        p = next_prime (p + 2)
    return p


def genere_courbe (p) :
    a = GF(p).random_element()
    b = GF(p).random_element()    
    while courbe_elliptique([a,b]) == False :
        a = GF(p).random_element()
        b = GF(p).random_element()
    return [a,b]


def param_public () :
    p = genere_premier ()
    courbe = genere_courbe (p)
    P = trouve_point ( courbe, p )

    print 'nombre premier :', p
    print 'point :', P
    print 'courbe : y^2 = x^3 +', courbe[0],'x + ', courbe[1]

    return p, P, courbe



def echange_public (a, P, p, courbe) :
    return multiple(a, P, courbe)


def plus_un (p, courbe, P, kP) :
    return somme(P, kP, courbe)


def bruteforce(p, courbe, P, aP, bP, borne) :
    current = P
    for i in IntegerRange(borne) :
        if i%20 == 0 :
            print 'i=',i
	if i <> 0 and i%200 == 0 :
	    print 'c\'est un peu long...'
        if current == aP :
            print('a')
            return i+1
        if current == bP :
            print('b')
            return i+1
        current = plus_un(p, courbe, P, current)


def point_en_cle (point) :
    liste_a = ZZ(point[0]).digits(27)
    liste_b = ZZ(point[1]).digits(27)
    return numlist2string(liste_a + liste_b)