hilpers


  hilpers > sci.* > sci.maths

 #1  
18/04/2017, 22h15
Julien Arlandis
Le but de cet article est de proposer une méthode sécurisée
d?authentification distribuée sur un réseau de serveurs publiques. La
base de données d?authentification est accessible en lecture seule par
tout un chacun. Voici l'algorithme que j'ai imaginé, je le soumet à
votre analyse.

Étape 1 : l'inscription :

Alice demande au serveur de s?inscrire sur le réseau.

Le serveur sauvegarde les paramètres d?authentification d?Alice dans
une Data définie comme suit, puis la renvoie au client :
Data = {
?UserID?:?Alice@DistributedNetwork?,
?DateInscription?:?10-10-2017?,
?PublicKey?:{ ?value?:null, ?keyLength?:1024,
?hashAlgorithm?:?sha512? }
}

Alice génère une paire de clé RSA à partir de son mot de passe au
moyen de l?algorithme suivant :

hash = hashAlgorithm(UserID + password + DateInscription)

[PrivateKey, PublicKey] = function generateRSAkeys(hash) {
p = INTEGER(hash)
SI (p modulo 2) == 0 alors p = p + 1
TANT QUE testPrimalite(p) is false
p = p + 2
FIN TANT QUE

q = INTEGER(hashAlgorithm(p))
SI (q modulo 2) == 0 alors q = q + 1
TANT QUE testPrimalite(q) is false
q = q + 2
FIN TANT QUE

n = p * q
détermine e, d (voir théorème RSA)
Retourne [(n,e), (p,q,d)]
}
Alice retourne au serveur sa clef publique ainsi calculée :
PublicKey.value = (n,e);

Étape 2 : l'authentification :

Alice demande au serveur de s?authentifier en indiquant son identifiant
Alice@DistributedNetwork.

Le serveur envoit à Alice un token aléatoire ainsi que sa Data
d?authentification.

Alice calcule sa clef privée à l?aide de la fonction :
PrivateKey = generateRSAkeys( hashAlgorithm(UserID + password +
DateInscription) )

Alice crypte le token avec sa clef privée :
tokenCrypt = EncryptRSA(token, PrivateKey, PublicKey.KeyLength)

Alice envoie tokenCrypt au serveur

Le serveur décrypte tokenCrypt avec la clef publique d?Alice :
tokenDecrypt = DecryptRSA(tokenCrypt, PublicKey, PublicKey.KeyLength)

Si tokenDecrypt == token alors l?authentification est réussie.

 #2  
20/04/2017, 12h52
Olivier Miakinen
Bonjour,

Je ne suis pas un expert en algorithmes de chiffrement (j'en connais
juste assez pour trouver les failles des tentatives de remy, mais
ça c'est toujours très facile). Du coup je ne répondrai qu'à des
points de datail.

Le 18/04/2017 22:15, Julien Arlandis a écrit :
[..]
> Data = {
> ?UserID?:?Alice@DistributedNetwork?,
> ?DateInscription?:?10-10-2017?,


À 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".

[..]
> TANT QUE testPrimalite(p) is false
> p = p + 2
> FIN TANT QUE


Comme je le disais, je ne suis pas un expert en algorithmes de
chiffrement. Mais je me demande si cette méthode ne présente pas
une faiblesse, en donnant à certains nombres premiers une plus
grande probabilité d'être choisis qu'à d'autres. Par exemple,
un nombre premier qui serait précédé de 19 nombres composés
aurait 10 fois plus de chances d'être choisi qu'un nombre
qui serait le second d'une paire de premiers jumeaux.

> q = INTEGER(hashAlgorithm(p))
> SI (q modulo 2) == 0 alors q = q + 1
> TANT QUE testPrimalite(q) is false
> q = q + 2
> FIN TANT QUE


Idem.

Je donne un exemple : pour tout N, le plus petit nombre premier
supérieur à N!+N est assuré d'avoir au moins N+1 nombres composés
avant lui.

> [...]


Aucun commentaire sur la suite.
 #3  
20/04/2017, 14h01
remy
a croire que je vous manque,commence a trouve quelque chose sur

[..]

a après on verra ,tu peut même essayer de trouve une référence sur la
relation (b+c)^n=... a la fin du préambule

remy
ps : ta jamais rien trouve sauf de sordide histoire de présentation
 #4  
20/04/2017, 14h28
Julien Arlandis
Bonjour,

Le 20/04/2017 à 12:52, Olivier Miakinen a écrit :
> Bonjour,
> Je ne suis pas un expert en algorithmes de chiffrement (j'en connais
> juste assez pour trouver les failles des tentatives de remy, mais
> ça c'est toujours très facile). Du coup je ne répondrai qu'à des
> points de datail.
> Le 18/04/2017 22:15, 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.

> Comme je le disais, je ne suis pas un expert en algorithmes de
> chiffrement. Mais je me demande si cette méthode ne présente pas
> une faiblesse, en donnant à certains nombres premiers une plus
> grande probabilité d'être choisis qu'à d'autres. Par exemple,
> un nombre premier qui serait précédé de 19 nombres composés
> aurait 10 fois plus de chances d'être choisi qu'un nombre
> qui serait le second d'une paire de premiers jumeaux.


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é.

> Idem.
> Je donne un exemple : pour tout N, le plus petit nombre premier
> supérieur à N!+N est assuré d'avoir au moins N+1 nombres composés
> avant lui.


En lisant ton dernier paragraphe je n'avais pas compris, mais avec cet
exemple ça devient plus clair et je pense que tu as mis le doigt ur un
problème intéressant. 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.

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

Qu'en penses tu ?
 #5  
20/04/2017, 15h13
remy
> Qu'en penses tu ?

qu'il et complètement incompétent

regarde

[..]
ou fait une recherche avec comme mot clef pki

remy
 #6  
20/04/2017, 15h23
Benoit.d
"Julien Arlandis" a écrit dans le message de groupe de discussion :
yt1IBl3kHgY4LAJTF7fx7x9JNxo@jntp...

> Le but de cet article est de proposer une méthode sécurisée d?authentification
> distribuée sur un réseau de serveurs publiques.


[...]

> [Alice <=> Serveur....]


J'ai pas compris: En quoi l'authentification est distribuée ?

> j'aimerais implémenter comme stratégie d'authentification sur les serveurs
> JNTP


T'es en http il me semble: Pourquoi pas un classique Kerberos/NTLM via TLS
si besoin ?
 #7  
20/04/2017, 15h27
Samuel DEVULDER
On Thu, 20 Apr 2017 12:52:46 +0200, Olivier Miakinen
<om+news> wrote:
> À 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".


Et sans doute l'exprimer en temps universel pour que deux personne
dans des fuseaux horaires différents aient la même date.
 #8  
20/04/2017, 16h25
Julien Arlandis
Le 20/04/2017 à 15:23, "Benoit.d" a écrit :
> "Julien Arlandis" a écrit dans le message de groupe de discussion :
> yt1IBl3kHgY4LAJTF7fx7x9JNxo@jntp...
> [...]
> J'ai pas compris: En quoi l'authentification est distribuée ?


Parce que la Data qui contient les données d'authentification est à la
fois publique et distribuée sur un réseau de serveurs. Tu t'inscris sur
un serveur A et tu t'authentifies sur un serveur B ou C.

>> j'aimerais implémenter comme stratégie d'authentification sur les serveurs
>> JNTP

> T'es en http il me semble: Pourquoi pas un classique Kerberos/NTLM via TLS
> si besoin ?


Parce que je veux une méthode d'authentification distribuée.
 #9  
20/04/2017, 17h47
Olivier Miakinen
Le 20/04/2017 14:28, Julien Arlandis a écrit :
> 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.

[..]
> 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.
 #10  
20/04/2017, 17h55
Olivier Miakinen
Le 20/04/2017 17:47, j'écrivais :
> 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)


Un code plus simple pour faire la même chose :
p = 3 * INTEGER(hash) + 1
SI (p modulo 2) == 0 ALORS p = p + 1

.... mais ce code devrait être accompagné d'un gros
commentaire expliquant en quoi cela fait une bijection
de l'ensemble des nombres entiers vers l'ensemble des
nombres de la forme 6n+1 ou 6n+5 !
 #11  
20/04/2017, 18h55
Benoit.d
"Julien Arlandis" a écrit dans le message de groupe de discussion :
Z0_ciF6Xc9R0t_0HW8y7Ycc8kWo@jntp...

>Le 20/04/2017 à 15:23, "Benoit.d" a écrit :
> Parce que la Data qui contient les données d'authentification est à la
> fois publique et distribuée sur un réseau de serveurs. Tu t'inscris sur un
> serveur A et tu t'authentifies sur un serveur B ou C.


Ah ok. Bon moi, j'aurais plutôt dis redondé ou balancé
Distribué, je m'attend à trouver des problématiques de routage, de découpage
de processus, de synchronisation, de tolérance à la panne, ... Bref en
général, ce genre de trucs.

La logique d'accès à ta source de données "distribuées" n'est pas décrite,
ni un problème pour toi en fait. Ce qui t'intéresse, c'est surtout l'algo de
chiffrage et le protocole d'authentification (qui n'est pas distribué en
lui-même).

>>> j'aimerais implémenter comme stratégie d'authentification sur les
>>> serveurs JNTP

>> T'es en http il me semble: Pourquoi pas un classique Kerberos/NTLM via
>> TLS si besoin ?

> Parce que je veux une méthode d'authentification distribuée.


Si j'ai compris, ta distribution consiste juste à ce que chaque serveur du
réseau puisse prendre en charge une demande d'authentification. Je persiste
à penser qu'un Kerberos configuré sur chaque serveur ferait ça très bien
(quitte à interfacer ta data source maison via un pseudo service ldap qui
serait consommé par les serveurs). Avec un service d'annuaire standard, ce
serait bien sûr plus simple. Mais bon, j'ai sans doute pas tous les bouts et
contraintes de ton problème.

Enfin, ça devient très hors charte tout ça :)
 #12  
20/04/2017, 20h05
Julien Arlandis
Le 20/04/2017 à 17:47, Olivier Miakinen a écrit :
> Le 20/04/2017 14:28, Julien Arlandis a écrit :
> 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.


Y a qu'à reprendre la définition qu'on avait donné au champ JNTP
Data.InjectionDate :

3.4.3. Data.InjectionDate (String, obligatoire)

Contient la date au format UTC à laquelle le paquet a été émis sur
le réseau JNTP.
Data.InjectionDate = AAAA"-" MM "-" JJ "T" HH ":" MM ":" SS "Z"

cf
<https://raw.githubusercontent.com/Julien-Arlandis/phpNemoServer/master/jntp_rfc-v0.21.4.txt>

> 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.


Je suis d'accord, mais vu qu'on ne connait pas de formule explicite pour
construire l'ensemble des nombres premiers, toute fonction qui a pour
objectif de rechercher un nombre premier se heurtera à ce même argument,
non?

> 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.


Oui.

[..]
> 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.


L'espace serait doublé si l'intervalle n'était pas borné, il faudra
d'ailleurs penser à boucler si on dépasse la limite supérieure.

[..]
> 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)]
> }


Le random me plait moins car il s'agit d'une fonction déterministe à
écrire à travers laquelle peut se cacher une éventuelle faille.
 #13  
21/04/2017, 12h48
Olivier Miakinen
Le 20/04/2017 20:05, Julien Arlandis a écrit :
> Y a qu'à reprendre la définition qu'on avait donné au champ JNTP
> Data.InjectionDate :
> 3.4.3. Data.InjectionDate (String, obligatoire)
> Contient la date au format UTC à laquelle le paquet a été émis sur
> le réseau JNTP.
> Data.InjectionDate = AAAA"-" MM "-" JJ "T" HH ":" MM ":" SS "Z"


Tout simplement, oui. Cette définition est d'ailleurs conforme à
la norme ISO 8601. ;-)

> Je suis d'accord, mais vu qu'on ne connait pas de formule explicite pour
> construire l'ensemble des nombres premiers, toute fonction qui a pour
> objectif de rechercher un nombre premier se heurtera à ce même argument,
> non?


Pas si, comme je le suggérais, tu fais une itération dans l'espace
beaucoup plus ouvert des chaînes « UserID + password + DateInscription
+ seed » et que tu n'appliques le hash qu'au résultat, au lieu de
faire une itération sur les résultats successifs du hash.

Et encore moins si tu fais intervenir une part de hasard, mais tu y
sembles opposé.

>> 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.

> L'espace serait doublé si l'intervalle n'était pas borné, il faudra
> d'ailleurs penser à boucler si on dépasse la limite supérieure.


Ok. Dans ce cas, tu peux quand même simplifier ton code avec :
p = INTEGER(hash) | 1
(« | » représentant le « ou binaire »)

Et bien que ça restreigne encore l'espace des nombres premiers, je
me demande s'il n'est pas conseillé d'éviter des nombres trop petits.
Cela donnerait, pour un hash de 512 bits :
p = INTEGER(hash) | 1 | (1 << 511)
(« << » représentant le « décalage à gauche », c.-à-d. 1 << 511 = 2^511)
 #14  
21/04/2017, 14h49
Julien Arlandis
Le 21/04/2017 à 12:48, Olivier Miakinen a écrit :
> Le 20/04/2017 20:05, Julien Arlandis a écrit :
> Tout simplement, oui. Cette définition est d'ailleurs conforme à
> la norme ISO 8601. ;-)


Problème réglé donc.

> Pas si, comme je le suggérais, tu fais une itération dans l'espace
> beaucoup plus ouvert des chaînes « UserID + password + DateInscription
> + seed » et que tu n'appliques le hash qu'au résultat, au lieu de
> faire une itération sur les résultats successifs du hash.
> Et encore moins si tu fais intervenir une part de hasard, mais tu y
> sembles opposé.


L'introduction du seed me plait bien, et je pense que je vais partir sur
cette idée.

> Ok. Dans ce cas, tu peux quand même simplifier ton code avec :
> p = INTEGER(hash) | 1
> (« | » représentant le « ou binaire »)


Oui.

> Et bien que ça restreigne encore l'espace des nombres premiers, je
> me demande s'il n'est pas conseillé d'éviter des nombres trop petits.
> Cela donnerait, pour un hash de 512 bits :
> p = INTEGER(hash) | 1 | (1 << 511)
> (« << » représentant le « décalage à gauche », c.-à-d. 1 << 511 = 2^511)


On pourrait rajouter une condition du type :

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

N étant à déterminer.

Je propose pour une clef de m bits la valeur N = m-10 qui convient à 1023
hash sur 1024.

Pour l'implémentation, on peut partir d'un projet existant qui permet de
générer une paire de clefs RSA, côté client j'ai trouvé par exemple :
[..]

en PHP, comment faire pour gérer les très grands nombres, une idée ?
 #15  
21/04/2017, 15h10
Olivier Miakinen
[copie et suivi vers fr.comp.lang.php]

Le 21/04/2017 14:49, Julien Arlandis a écrit :
> en PHP, comment faire pour gérer les très grands nombres, une idée ?


RTFM ? <http://php.net/manual/fr/refs.math.php>

D'après la doc, il semble que tu aies le choix entre BCMath et GMP,
tous deux ayant une fonction qui calcule une puissance en arithmétique
modulaire :
<http://php.net/manual/fr/function.bcpowmod.php>
<http://php.net/manual/fr/function.gmp-powm.php>


Discussions similaires
Grands nombres pour RSA en PHP (was: Algorithme d?authentification distribuée)

Requête distribuée sur un 6.5

Requête distribuée

transaction distribuée


Fuseau horaire GMT +2. Il est actuellement 20h42. | Privacy Policy