Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

différenciation aléatoire / chiffré

41 réponses
Avatar
Kevin Denis
Bonjour,

j'ai souvent lu qu'un critère pour un bon chiffrement repose
sur le fait qu'il ne doit pas être possible de différencier de
l'aléatoire du chiffré.

Est ce que quelqu'un dispose d'un pointeur vers une doc
"officielle" affirmant ce point? Je suis assez d'accord avec ce
principe, mais je ne trouve pas de justificatif style document
de l'ANSSI ou équivalent.

Dans un deuxième temps, quelles sont les conséquences inverse?
C'est à dire que si je suis capable de différencier un flux
chiffré d'un flux aléatoire, qu'est ce que je peux en déduire
sur le procédé de chiffrement? Une faiblesse théorique, ou bien
d'autres conclusions sont à tirer?

Merci
--
Kevin

10 réponses

1 2 3 4 5
Avatar
remy
xtof.pernod a écrit :
Le 23/05/2010 18:20, Emile a fait rien qu'à écrire :
On 15 mai, 15:38, Kevin Denis wrote:
j'ai souvent lu qu'un critère pour un bon chiffrement repose
sur le fait qu'il ne doit pas être possible de différencier de
l'aléatoire du chiffré.

Kevin



Que pensez vous du "Test Universel" qui permet de chiffrer suivan t
une échelle normalisée le manque du caractère aléatoire d'une série de
nombres par rapport à l'aléatoire parfait.



Ben.. à froid, comme ça, une seule mesure pour déterminer si on a affaire
à de l'aléa (ou pas), c'est surprenant. Dans le sens: ça serait t rop beau.

Mais bon, faut voir.


> Voir: http://homeusers.brutele.be/bruno.musyck/WikiTestUniversel.pdf .
> avoir plus d'info sur l'algorithme SED, voir:
http://fr.wikipedia.org/wiki/SED_%28algorithme%29.

"mathématiquement les plus proches de l'aléatoire parfait" :

Ca, ça me cause pas. Déja, "aléatoire", c'est pas facile à
trouver une def' qui convienne à tout le monde, mais "parfait",
je décroche.




au hasard de la cuisine avec des nombres premier

http://remyaumeunier.chez-alice.fr/gene.php
http://remyaumeunier.chez-alice.fr/testAlea.php



"vu la structure scientifiquement établie du test universel et les
tests expérimentaux afférents à ce test, "

Quelque lien, là dessus ?..


Voir également le chapitre Challenge.



Ouaiiis !!! Une jolie montre en or !?!
Vaut-elle plus que les 100$ du Random Million Digit challenge ? ;)




un lien ?

merci remy



remy


--
http://remyaumeunier.chez-alice.fr/
Avatar
remy
remy a écrit :
xtof.pernod a écrit :
Le 23/05/2010 18:20, Emile a fait rien qu'à écrire :
On 15 mai, 15:38, Kevin Denis wrote:
j'ai souvent lu qu'un critère pour un bon chiffrement repose
sur le fait qu'il ne doit pas être possible de différencier de
l'aléatoire du chiffré.

Kevin



Que pensez vous du "Test Universel" qui permet de chiffrer suiva nt
une échelle normalisée le manque du caractère aléatoire d'une série de
nombres par rapport à l'aléatoire parfait.



Ben.. à froid, comme ça, une seule mesure pour déterminer si on a affaire
à de l'aléa (ou pas), c'est surprenant. Dans le sens: ça serait trop
beau.

Mais bon, faut voir.


> Voir: http://homeusers.brutele.be/bruno.musyck/WikiTestUniversel.pd f.
> avoir plus d'info sur l'algorithme SED, voir:
http://fr.wikipedia.org/wiki/SED_%28algorithme%29.

"mathématiquement les plus proches de l'aléatoire parfait" :

Ca, ça me cause pas. Déja, "aléatoire", c'est pas facile à
trouver une def' qui convienne à tout le monde, mais "parfait",
je décroche.




au hasard de la cuisine avec des nombres premier

http://remyaumeunier.chez-alice.fr/gene.php
http://remyaumeunier.chez-alice.fr/testAlea.php



"vu la structure scientifiquement établie du test universel et les
tests expérimentaux afférents à ce test, "

Quelque lien, là dessus ?..


Voir également le chapitre Challenge.



Ouaiiis !!! Une jolie montre en or !?!
Vaut-elle plus que les 100$ du Random Million Digit challenge ? ;)




un lien ?




ok j'ai trouvé et lu trop vite

The Payoff

The first person to achieve the challenge, while staying within the
spirit of the challenge, will receive a prize of $100.




--
http://remyaumeunier.chez-alice.fr/
Avatar
xtof.pernod
Le 25/05/2010 00:17, Mehdi Tibouchi a fait rien qu'à écrire :
"xtof.pernod" wrote in message
<4bfae24c$0$27581$:
D'où vient le 129ème octet ?


Si N dépasse un peu 2^1024, il ne tient pas dans 128 octets, donc il
faut mettre un 129ème. Peut-être qu'il faut appeler 2^1024 + 643 un
nombre de 1025 bits, cela dit; je n'ai pas d'avis ferme sur la question.



Du point de vue de l'arithmétique / de l'implémentation, si N >= 2^1024,
il faut 1025 bits au moins. Trivialemand =)

Après, s'il y a une nomenclature officielle..

(...)
Soit une chaine de (n) bits. Sans perte de généralité, on peut se dire
que n est un multiple d'une puissance de 2, de 8, bref, tout ce qui
peut simplifier le raisonnement / l'implémentation éventuelle.

Existe-t-il un algorithme qui dise: "chiffré" ou "non chiffré" par RSA,
l'un et/ou l'autre, avec une probabilité de succès supérieure à 1/2.



Je ne suis pas sûr de comprendre la question, mais s'il s'agit de savoir



Si, si, impeccable.

si on peut distinguer un chiffré RSA d'un nombre aléatoire entre 1 et N,
la réponse est non pour RSA « text-book » : la fonction RSA est une
permutation de (Z/NZ)^*, donc tous les nombres entre 1 et N premiers à N
sont des chiffrés valides.



Ah ben oui, bon sang, c'est bien sûr.

Question 4 (désolé:)
Et équiprobables ?

Exemple, si le(s) message(s) est constitué de texte ascii, les caractères
affichables uniquement. Est-ce que tous les résidus du modules sont
atteints, est-ce que l'histogramme est (à peu-près) plat, etc..

A vue de nez, je dirais non, à moins que N = p.q ou M ou e soi(en)t
d'une [certaine] taille (?) au moins, mais s'il y a une preuve simple
et élégante, je prends !

[Certes, on peut compresser le message, mais ça ne fait que compliquer
les calculs, sans vraiment s'affranchir du problème. Je passe aussi sur
le padding, parce que sinon c'est trop facile, comme dit ci-après]


Si on regarde autre chose que RSA text-book, il faut préciser de quelle
façon sont formatés les messages.



(Je l'ai peut-être pas dit clairement, mais j'essaye de faire abstraction
de tout ce qui est lié à l'implémentation -et qui a son importance-,
quitte à employer une version dégradée/affaiblie, en toute connaissance
de cause, juste pour (sa-)voir.

Bon, apparemment, c'est pas si simple !)


Pour RSA-OAEP, je crois que la
situation est la même, tout élément de (Z/NZ)^* est un chiffré valide. En



Avec un padding ('remplissage' ?) aléatoire, ça se tient..
Merci.

revanche ce n'est pas le cas avec PKCS#1v1.5, où il peut se passer des
choses amusantes (on ne sait pas construire de distingueur, mais si l'on
dispose d'un oracle qui distingue les chiffrés valides, ce qui arrivait
dans beaucoup d'implémentations de SSL à la fin des années 90, alors on
peut déchiffrer : attaque de Bleichenbacher).




--
christophe.
Avatar
xtof.pernod
Le 25/05/2010 09:50, remy a fait rien qu'à écrire :
remy a écrit :
(...)







au hasard de la cuisine avec des nombres premier

http://remyaumeunier.chez-alice.fr/gene.php
http://remyaumeunier.chez-alice.fr/testAlea.php





Terrible ! Je me suis bien marré à:

"j'ai recupéré quelque kilot de bits "radioactif" ici l'on trouve
de tout sur internet"

Des bits radioactifs, c'est conceptuel ! Bon, je fwd: ça à mon boss,
et avec la prime de risque que je manquerai pas de toucher:

-Tavernier, que diable: tournée générale, et en Guinness, svp =)




"vu la structure scientifiquement établie du test universel et les
tests expérimentaux afférents à ce test, "

Quelque lien, là dessus ?..


Voir également le chapitre Challenge.



Ouaiiis !!! Une jolie montre en or !?!
Vaut-elle plus que les 100$ du Random Million Digit challenge ? ;)




un lien ?




ok j'ai trouvé et lu trop vite




T'inquiète.

Seul Chuck Norris peut lâcher 3 mots dans un moteur de recherche
en moins de 35 minutes.

--
christophe.
Avatar
remy
xtof.pernod a écrit :
Le 25/05/2010 09:50, remy a fait rien qu'à écrire :
remy a écrit :
(...)







au hasard de la cuisine avec des nombres premier

http://remyaumeunier.chez-alice.fr/gene.php
http://remyaumeunier.chez-alice.fr/testAlea.php





Terrible ! Je me suis bien marré à:



et à part cela quelque chose de particulier
tu as le générateur de grands nombres premiers + le code + les tests

maintenant tu peux toujours dire qu'il n'y a pas une infinité de nombre s
premiers et que le bit de poids faible du reste d'un nombre premier par
un deuxième nombre premier différent est quelque chose de prédictib ilité

mais comme l'aléa est quelque chose, de comme ,tu l'as dit , de pas trè s
bien défini ,on va s'éviter un débat qui ne pourra qu'être stér ile ,je
te propose plutôt de t'attaquer à l'algo asymétrique posté un peu plus
haut, tu as tout ce qu'il te faut ,je peux même te pondre 5 lignes de
code,mais avant il va falloir m'expliquer ce que tu ne comprends pas

au plaisir de te lire



remy


--
http://remyaumeunier.chez-alice.fr/
Avatar
xtof.pernod
Le 25/05/2010 14:57, xtof.pernod a fait rien qu'à écrire :
[distingueur de chiffrés RSA]



Bon, ça y est je suis convaincu (c'est dingue comme 2 j. de
progra permettent de s'affranchir de 10mn de lecture..) :

Pour que toutes les valeurs possibles soient représentées,
avec la même probabilité, dans un chiffré RSA, il faut que
le module (N) soit codés sur un nombre de bits multiple de
8 (pas de pb.) ET que les 8 premiers soient à 1.

Sinon, les valeurs supérieures à l'octet de poids fort sont
sous-représentées. (et hop, un distingueur trivial =)

Merci pour la discussion,

--
christophe.
Avatar
xtof.pernod
Le 25/05/2010 15:49, remy a fait rien qu'à écrire :
xtof.pernod a écrit :
Le 25/05/2010 09:50, remy a fait rien qu'à écrire :
remy a écrit :
(...)











Terrible ! Je me suis bien marré à: [bits radio-actifs]



et à part cela quelque chose de particulier



Non non, c'est bon -- 2 cafés, l'addition.

tu as le générateur de grands nombres premiers + le code + les tests

maintenant tu peux toujours dire qu'il n'y a pas une infinité de nombres
premiers



Ca m'étonnerait quand même un peu que je dise ça.
Sous la torture, ou sous produits psychotropes, peut-être..

et que le bit de poids faible du reste d'un nombre premier par
un deuxième nombre premier différent est quelque chose de prédictibilité



Désolé, je suis pas très bien sûr de suivre toi.
"Reste", donc je suppose que tu parles de division euclidienne ?

Et tu prédis comment, le bit de poids faible ?

mais comme l'aléa est quelque chose, de comme ,tu l'as dit , de pas très
bien défini ,on va s'éviter un débat qui ne pourra qu'être stérile ,je
te propose plutôt de t'attaquer à l'algo asymétrique posté un peu plus
haut, tu as tout ce qu'il te faut ,je peux même te pondre 5 lignes de



Ouaiiis ! Vas-y Remy, ponds-moi cinq lignes, ça sera toujours ça de pris !

code,mais avant il va falloir m'expliquer ce que tu ne comprends pas



Ben tiens: si t'as pigé l'article sus-cité sur un "test universel",
tu peux me l'expliquer.. Perso, c'est pas avec ça que je vais pouvoir
l'implémenter.

Apparemment, ça serait basé sur la loi de Poisson (que ça m'étonnerait
pas), mais si c'est juste ça, on peut facilement (trivialement même ;)
générer un fichier qui obtiendra un bon 'score', tout en étant absolu-
ment pas aléatoire. (hautement compressible, par ex.)

Rien d'universel, donc, ou j'ai loupé une marche.


remy





--
christophe.
Avatar
Paul Gaborit
À (at) Wed, 26 May 2010 23:16:59 +0200,
"xtof.pernod" écrivait (wrote):

Ben tiens: si t'as pigé l'article sus-cité sur un "test universel",
tu peux me l'expliquer.. Perso, c'est pas avec ça que je vais pouvoir
l'implémenter.

Apparemment, ça serait basé sur la loi de Poisson (que ça m'étonnerait
pas), mais si c'est juste ça, on peut facilement (trivialement même ;)
générer un fichier qui obtiendra un bon 'score', tout en étant absolu-
ment pas aléatoire. (hautement compressible, par ex.)

Rien d'universel, donc, ou j'ai loupé une marche.



Si un test "vraiment" universel existait, on pourrait l'utiliser pour
implémenter un générateur "vraiment" aléatoire : à chaque pas, le
générateur utilise le testeur pour trouver, par essais et erreurs, une
prochaine valeur "vraiment" aléatoire... ;-)

--
Paul Gaborit - <http://perso.mines-albi.fr/~gaborit/>
Avatar
remy
xtof.pernod a écrit :
Le 25/05/2010 15:49, remy a fait rien qu'à écrire :
xtof.pernod a écrit :
Le 25/05/2010 09:50, remy a fait rien qu'à écrire :
remy a écrit :
(...)











Terrible ! Je me suis bien marré à: [bits radio-actifs]



et à part cela quelque chose de particulier



Non non, c'est bon -- 2 cafés, l'addition.

tu as le générateur de grands nombres premiers + le code + les tes ts

maintenant tu peux toujours dire qu'il n'y a pas une infinité de nom bres
premiers



Ca m'étonnerait quand même un peu que je dise ça.
Sous la torture, ou sous produits psychotropes, peut-être..

et que le bit de poids faible du reste d'un nombre premier par
un deuxième nombre premier différent est quelque chose de prédic tibilité



Désolé, je suis pas très bien sûr de suivre toi.
"Reste", donc je suppose que tu parles de division euclidienne ?




bon ok
sous linux un terminal et tu tapes bc

24443%3623
2705

et dans 2705 tu prends l'un des bits de la décomposition en base 2 de
2705 tu prends celui qui te fait plaisir à titre perso j'éviterai le
dernier mais bon tu fais comme tu veux

ensuite tu changes les 2 nombres premiers et tu recommences

le seul moyen te casser mon générateur serait de démontrer
que le théorème sur les nombres jumeaux est faux
ou que la version généralisée de ce théorème est fausse
les matheux appellent cela la conjecture de Polignac


te te te je ne remets pas le couvert



Et tu prédis comment, le bit de poids faible ?

mais comme l'aléa est quelque chose, de comme ,tu l'as dit , de pas très
bien défini ,on va s'éviter un débat qui ne pourra qu'être sté rile ,je
te propose plutôt de t'attaquer à l'algo asymétrique posté un peu plus
haut, tu as tout ce qu'il te faut ,je peux même te pondre 5 lignes d e



Ouaiiis ! Vas-y Remy, ponds-moi cinq lignes, ça sera toujours ça de pris !

code,mais avant il va falloir m'expliquer ce que tu ne comprends pas



Ben tiens: si t'as pigé l'article sus-cité sur un "test universel",
tu peux me l'expliquer.. Perso, c'est pas avec ça que je vais pouvoir
l'implémenter.




je sais que j'avais des difficultés à me faire comprendre
mais là franchement je ne savais pas que j'étais aussi mauvais



donc l'on oublie mon générateur de nombres aléatoires
ce truc est vieux de plusieurs années

donc je suis à la recherche d'un retour sur

******************************
alice
p34.78956123
rx
d=p+r

alice envoie d à bob

bob
x000
y
m=((d-x)*y+d*y+x)
bob envoie m à alice

puis alice recherche un entier dans m en faisant varier
r0 (r0=1,2,3,4,...) si n est entier (partie décimale n égale à 0) bingo



n=m-r0*p

puis calcule r1
r1=(n-r*r0)/(1-(r0/2))
*******************************

alice et bob partagent un secret commun
(x=r1 et y=r0) eve ne voit que d et m


remy



--
http://remyaumeunier.chez-alice.fr/
Avatar
remy
remy a écrit :
xtof.pernod a écrit :
Le 25/05/2010 15:49, remy a fait rien qu'à écrire :
xtof.pernod a écrit :
Le 25/05/2010 09:50, remy a fait rien qu'à écrire :
remy a écrit :
(...)











Terrible ! Je me suis bien marré à: [bits radio-actifs]



et à part cela quelque chose de particulier



Non non, c'est bon -- 2 cafés, l'addition.

tu as le générateur de grands nombres premiers + le code + les te sts

maintenant tu peux toujours dire qu'il n'y a pas une infinité de no mbres
premiers



Ca m'étonnerait quand même un peu que je dise ça.
Sous la torture, ou sous produits psychotropes, peut-être..

et que le bit de poids faible du reste d'un nombre premier par
un deuxième nombre premier différent est quelque chose de prédi ctibilité



Désolé, je suis pas très bien sûr de suivre toi.
"Reste", donc je suppose que tu parles de division euclidienne ?






après relecture

bon ok
sous linux un terminal et tu tapes bc

24443%3623
2705

et dans 2705 tu prends l'un des bits de la décomposition en base 2 de
2705 tu prends celui qui te fait plaisir à titre perso j'éviterai l e
dernier mais bon tu fais comme tu veux

ensuite tu changes les 2 nombres premiers et tu recommences

un moyen te casser mon générateur serait de démontrer
que le théorème sur les nombres jumeaux est faux
ou que la version généralisée soit fausse
les matheux appellent cela la conjecture de Polignac


te te te je ne remets pas le couvert



Et tu prédis comment, le bit de poids faible ?

mais comme l'aléa est quelque chose, de comme ,tu l'as dit , de pas très
bien défini ,on va s'éviter un débat qui ne pourra qu'être st érile ,je
te propose plutôt de t'attaquer à l'algo asymétrique posté un peu plus
haut, tu as tout ce qu'il te faut ,je peux même te pondre 5 lignes de



Ouaiiis ! Vas-y Remy, ponds-moi cinq lignes, ça sera toujours ça d e
pris !

code,mais avant il va falloir m'expliquer ce que tu ne comprends pas



Ben tiens: si t'as pigé l'article sus-cité sur un "test universel" ,
tu peux me l'expliquer.. Perso, c'est pas avec ça que je vais pouvoi r
l'implémenter.




je sais que j'avais des difficultés à me faire comprendre
mais là franchement je ne savais pas que j'étais aussi mauvais





donc l'on oublie mon générateur de nombres aléatoires
ce truc est vieux de plusieurs années

donc je suis à la recherche d'un retour sur

******************************
alice
p34.78956123
rx
d=p+r

alice envoie d à bob

bob
x000
y
m=((d-x)*y+d*y+x)
bob envoie m à alice

puis alice recherche un entier dans m en faisant varier
r0 (r0=1,2,3,4,...) si n est entier (partie décimale n égale à 0) bingo



n=m-r0*p

puis calcule r1
r1=(n-r*r0)/(1-(r0/2))
*******************************

alice et bob partagent un secret commun
(x=r1 et y=r0/2) eve ne voit que d et m


remy





--
http://remyaumeunier.chez-alice.fr/
1 2 3 4 5