Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > fr.sci.maths > #26668

Re: Algorithme d’authentification distribuée

Show all headers | View raw

Le 20/04/2017 14:28, Julien Arlandis a écrit :
>> 
>> À moins de te limiter à un contexte franco-français, il me
>> semble qu'il vaudrait mieux exprimer la date selon un format
>> compatible avec la norme ISO 8601 : soit "20171010" soit
>> "2017-10-10", mais pas "10-10-2017".
> 
> Oui tout à fait. Note qu'il ne s'agit pas de l'algorithme définitif mais 
> d'un premier brouillon en vue d'établir une preuve de concept que 
> j'aimerais implémenter comme stratégie d'authentification sur les 
> serveurs JNTP, et donc aussi comme méthode d'authentification pour 
> écrire sur usenet en passant par JNTP.

Définitif ou pas, choisir comme format de date JJ-MM-AAAA ou
MM-JJ-AAAA pour autre chose qu'un affichage localisé dans la langue d'un
utilisateur donné, ce sera toujours une mauvaise idée.

Tu as donné comme exemple 10-10-2017 qui est forcément le 10 octobre,
mais avec 10-09-2017 (ou du reste 09-10-2017) il serait impossible de
deviner /a priori/ si c'est le 9 octobre ou le 10 septembre.

> [...]
> 
> Pour qu'on soit sûr de parler de la même chose, j'explicite davantage 
> cette partie de l'algo.
> On part d'une chaine de caractère supposée unique qui contient le mot de 
> passe de l'utilisateur, on calcule son empreinte (disons en sha512 pour 
> l'exemple). Ceci nous permet de définir un nombre entier positif compris 
> entre 0 et 2^512-1. Dans le cas idéal d'une fonction de hashage parfaite 
> supposée sans collisions, tous les entiers compris dans cet intervalle 
> ont la même probabilité d'être sélectionnés. Si tu es d'accord jusque 
> là, le choix du nombre premier revient à choisir un nombre entier au 
> hasard inférieur à 2^521-1, et de l'incrémenter jusqu'à ce qu'il passe 
> avec succès le test de primalité.

Oui, c'était très clair et c'est bien ainsi que je l'ai compris.

> [...] La probabilité de tomber dans un intervalle I où 
> se suivent un grand nombre de nombres composés est plus grande que de 
> tomber dans un intervalle J où se suivent moins de nombres composés. De 
> fait le premier nombre premier situé juste à droite de l'intervalle I 
> aura plus de chances d'être sélectionné que le premier nombre premier 
> situé juste à droite du second intervalle J.

Voilà, c'est exactement ça.

> Plutôt que d'itérer directement sur q, je propose d'itérer sur la 
> fonction de hash comme suit :
> TANT QUE testPrimalite(q) is false
>  	SI (q modulo 2) == 0 alors q = q + 1
> 	q = INTEGER(hashAlgorithm(q))
> FIN TANT QUE

Je suis désolé, mais ça ne change rien au problème. Tu as toujours
des chaînes plus ou moins longues de q_0 -> q_1 -> q_2 -> ... -> q_n
avant d'arriver sur un q_n qui soit premier, et la probabilité de
tomber à l'intérieur d'une chaîne où se suivent un grand nombre de
composés est, là encore, plus grande que celle de tomber dans une
chaîne où se suivent moins de nombres composés.

Note que ton « q = q + 1 si q est pair », outre qu'il est inutile à
cet endroit, renforce encore le nombre de 'q' non premiers qui
donneront le même 'q' premier à la fin.


Je te propose deux idées pour éviter cet écueil. La première, je ne
sais pas si elle l'évite vraiment. Quant à la seconde, elle t'obligera
à ajouter deux nombres à la clé publique.

========================================================================

Première idée :

[PrivateKey, PublicKey] =
function generateRSAkeys(UserID, password, DateInscription) {
    seed = 0

    FAIRE :
        seed = seed + 1
        hash = hashAlgorithm(UserID + password + DateInscription + seed)
        p = 2 * INTEGER(hash) + 1
    TANT QUE testPrimalite(p) is false

    FAIRE :
        seed = seed + 1
        hash = hashAlgorithm(UserID + password + DateInscription + seed)
        q = 2 * INTEGER(hash) + 1
    TANT QUE testPrimalite(q) is false
	
    n = p * q
    détermine e, d (voir théorème RSA)
Retourne [(n,e), (p,q,d)]
}

Note 1 : Faire « p = 2 * INTEGER(hash) + 1 » au lieu de
 « p = INTEGER(hash) » suivi de « p = p + 1 si p est pair »
 double l'espace des nombres premiers accessibles.

Note 2 : On peut même sextupler cet espace en faisant :
    p = INTEGER(hash)
    SI (p modulo 2) == 0 ALORS p = 3 * p + 1
    SINON p = 3 * p + 2
 (si p = 2n choisir 6n+1, si p = 2n+1 choisir 6n+5)

Note 3 : Tu remarqueras que le q ne dépend plus directement
 du p, ce qui était aussi une faiblesse de ta première
 proposition.

========================================================================

Deuxième idée :

[PrivateKey, PublicKey] =
function generateRSAkeys(UserID, password, DateInscription) {
    FAIRE :
        sp = RANDOM()
        hash = hashAlgorithm(UserID + password + DateInscription + sp)
        p = 2 * INTEGER(hash) + 1
    TANT QUE testPrimalite(p) is false

    FAIRE :
        sq = RANDOM()
        hash = hashAlgorithm(UserID + password + DateInscription + sq)
        q = 2 * INTEGER(hash) + 1
    TANT QUE testPrimalite(q) is false

    n = p * q
    détermine e, d (voir théorème RSA)
Retourne [(n,e,sp,sq), (p,q,d)]
}


P.-S. : tu as inversé PublicKey et PrivateKey, et du coup moi
 aussi -- je te laisse corriger.
-- 
Olivier Miakinen

Back to fr.sci.maths | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Algorithme d’authentification distribuée Julien Arlandis <julien.arlandis@gmail.com> - 2017-04-18 20:15 +0000
  Re: Algorithme d’authentification distribuée Olivier Miakinen <om+news@miakinen.net> - 2017-04-20 12:52 +0200
    Re: Algorithme d’authentification distribuée remy <remy@fctpas.fr> - 2017-04-20 14:01 +0200
    Re: Algorithme d’authentification distribuée Julien Arlandis <julien.arlandis@gmail.com> - 2017-04-20 12:28 +0000
      Re: Algorithme d’authentification distribuée remy <remy@fctpas.fr> - 2017-04-20 15:13 +0200
      Re: Algorithme dauthentification distribuée Samuel DEVULDER <fake@fakeemailcom.invalid> - 2017-04-20 15:27 +0200
      Re: Algorithme d’authentification distribuée Olivier Miakinen <om+news@miakinen.net> - 2017-04-20 17:47 +0200
        Re: Algorithme d’authentification distribuée Olivier Miakinen <om+news@miakinen.net> - 2017-04-20 17:55 +0200
        Re: Algorithme d’authentification distribuée Julien Arlandis <julien.arlandis@gmail.com> - 2017-04-20 18:05 +0000
          Re: Algorithme d’authentification distribuée Olivier Miakinen <om+news@miakinen.net> - 2017-04-21 12:48 +0200
            Re: Algorithme d’authentification distribuée Julien Arlandis <julien.arlandis@gmail.com> - 2017-04-21 12:49 +0000
              Grands nombres pour RSA en PHP (was: Algorithme d’authentification distribuée) Olivier Miakinen <om+news@miakinen.net> - 2017-04-21 15:10 +0200
              Re: Algorithme d’authentification distribuée Olivier Miakinen <om+news@miakinen.net> - 2017-04-21 15:17 +0200
                Re: Algorithme d’authentification distribuée Julien Arlandis <julien.arlandis@gmail.com> - 2017-04-21 19:14 +0000
                Re: Algorithme d’authentification distribuée remy <remy@fctpas.fr> - 2017-04-25 09:42 +0200
  Re: Algorithme d’authentification distribuée "Benoit.d" <nobody@nowhere.com> - 2017-04-20 15:23 +0200
    Re: Algorithme d’authentification distribuée Julien Arlandis <julien.arlandis@gmail.com> - 2017-04-20 14:25 +0000
      Re: Algorithme d’authentification distribuée "Benoit.d" <nobody@nowhere.com> - 2017-04-20 18:55 +0200

csiph-web