Bienvenue sur IndexError.

Ici vous pouvez poser des questions sur Python et le Framework Django.

Mais aussi sur les technos front comme React, Angular, Typescript et Javascript en général.

Consultez la FAQ pour améliorer vos chances d'avoir des réponses à vos questions.

Idée d'implem pour l'ago baby-step giant-step (crypto)

+1 vote
En théorie des groupes, une branche des mathématiques, l'algorithme baby-step giant-step est
une série d'étapes bien définies pour calculer le logarithme discret.
Le problème du logarithme discret, sur lequel se basent la plupart des cryptosystèmes
modernes, est fondamental dans le domaine de la cryptographie à clé publique

wiki

Ok c'est cool, pas encore piger le rapport entre le log discret et la crypto mais on va leur faire confiance, apparemment ce truc pourrait servir à quelque chose !

Au travail :

algo :

Entrée: un groupe cyclique G d'ordre n, ayant un générateur α et un élément β.
Sortie: la valeur x satisfait \alpha^{x}=\beta.
m ← [√n]+1
Pour j tel que 0 ≤ j < m:    //Baby-Step
   Calculer αj et sauvegarder la paire (j, αj) dans une table de hashage. 
   Calculer α−m.
   γ ← β. (Faire γ = β)
Pour i = 0 à (m − 1):   //Giant-Step
   Vérifier si γ est le second composant (αj) d'une paire quelconque dans la table.
   Si oui, retourner im + j.
   Si non , γ ← γ • α−m.

Première tentative (foireuse) d'implem python :

def baby_giant_step(groupCycl, ordreN, genT, eltB):
        m = sqrt(n)+1
        j=0
        hashTable = []
        while (j<m): # Baby Step
                powTJ = pow(genT,j)
                hashTable.append(j, powTJ)
                powTM = pow(genT, (-m))
                # algo dit : γ ← β. (Faire γ = β)
                # Rq : Wtf, on balance quoi dans y??
                # et qui est B ??
                j = j + 1
        i = 0
        while (i<m-1): # Giant Step
                # Algo : Vérifier si γ est le second composant (αj) d'une paire quelconque dans la table.
                # Si oui, retourner im + j.
                # Si non , γ ← γ • α−m
                # Rq : Je trve ça impinable, surtout qu'on connaît toujours pas y ...
demandé 9-Dec-2015 par boblinux (3,092 points)
edité 9-Dec-2015 par boblinux

1 Réponse

+4 votes
 
Meilleure réponse

Crois le ou non, mais c'est pas si simple ton affaire.

Déjà la page wikipédia est pas franchement excellente, va plutôt voir ça qui est bien plus clair.

Ce qu'il faut comprendre c'est qu'on cherche x tel que a**x=b [mod n]. Un autre point, c'est que a**-m, ça veux dire en vrai inv_a**m [mod n] et que inv_a se définit par inv_a*a=1 [mod n] (voir ici et ).

Laissons les maths décanter un peu et voyons ton code.
Déjà, vire les while + incrément et utilise des for + range.
Ensuite, quand on dit 'hash table', il faut traduire dictionnaire en python, pas une liste.
Pour info, le but de l'algo c'est d'être plus rapide que du brut force en pré-calculant une partie du résultat. la table de hashage (dict) est utilisée pour accéder rapidement à ces pré-calculs, si on utilise une liste à reparcourir à chaque fois qu'on cherche dedans on perd tout l'intérêt de la manoeuvre.

Et comme je suis sympa, voilà comment je ferais :

def egcd(a, b):
    """ r, u, v tq r = a*u + b*v et r = gcd(a, b)

    source: https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide_%C3%A9tendu

    """
    r, u, v, r_, u_, v_ = a, 1, 0, b, 0, 1
    while r_:
        q = r / r_
        r, u, v, r_, u_, v_ = (r_, u_, v_,
                               r-q*r_, u-q*u_, v-q*v_)
    return r, u, v


def bsgs(n, a, b):
    """ x tq pow(a, x, n) = b [mod n]

    n: ordre
    a: generateur
    b: nb a inv

    source: https://math.berkeley.edu/~sagrawal/su14_math55/notes_shank.pdf

    """
    assert b % n
    r, inva, _ = egcd(a, n)
    assert r == 1

    m = int(n ** .5) + 1
    am = pow(inva, m, n)

    table = {pow(a, j, n): j for j in range(m)}
    Y = b
    for i in range(m):
        if Y in table:
            return i * m + table[Y]
        Y = (Y * am) % n
    print 'fuck'
    return 0

PS : Soit sympa, fais au moins l'effort de poser une question dans ton poste.

répondu 9-Dec-2015 par bubulle (2,226 points)
sélectionné 16-Dec-2015 par boblinux

il s'est cru sur /r/sametmax
:)

@Bubulle

PS : Soit sympa, fais au moins l'effort de poser une question dans ton
poste.

Dsl, je pensais que c'était implicite, à savoir que je galérais juste à implem l'ago, donc en gros c'était une demande d'un coup de pouce pour finir mon implem.

Laissons les maths décanter

Pourquoi donc? S'il faut faire des petits détours maths pour mieux cerner le pb, pourquoi pas !

Et comme je suis sympa, voilà comment je ferais

T sympa <3

Réponse validée !

...