A propos des clefs Nspire

→ **MyCalcs** profile · by **Ciwtron** » 12 Dec 2009, 18:03

Je me demandais si quelqu'un pouvait m'éclairer un peu sur les clefs qui codent les OS.
J'ai bien compris qu'elles étaient de grosse taille et qu'il était impossible de les forcer pour le moment.
Mais pourquoi (je ne sais plus qui) a dit que se serait peut-être possible dans quelque années? Et si quelqu'un pouvait aussi m'éclairer sur la manière donc sa se factoriser, parce que je comprends rien aux formules de Wikipedia, et sur combien de temps il nous faudrait actuellement pour les forcer.
J'en demande peu être un peu beaucoup mais je penses que ça pourrait être utile pour plusieurs personnes.

→ **MyCalcs** profile · by **critor** » 12 Dec 2009, 18:22

Ciwtron wrote:Je me demandais si quelqu'un pouvait m'éclairer un peu sur les clefs qui codent les OS.
J'ai bien compris qu'elles étaient de grosse taille et qu'il était impossible de les forcer pour le moment.
Mais pourquoi (je ne sais plus qui) a dit que se serait peut-être possible dans quelque années? Et si quelqu'un pouvait aussi m'éclairer sur la manière donc sa se factoriser, parce que je comprends rien aux formules de Wikipedia, et sur combien de temps il nous faudrait actuellement pour les forcer.
J'en demande peu être un peu beaucoup mais je penses que ça pourrait être utile pour plusieurs personnes.

Sur un ordinateur récent tout seul, la factorisation d'une clef TI 512 bits a pris plusieurs mois.

En faisant tourner des centaines d'ordinateurs simultanément sur la même clef 512 bits, nous n'avons en moyenne eu besoin que de quelques jours.

Une clef 512 bits est un nombre hexadécimal de 128 chiffres.
Une clef 1024 bits est un nombre hexadécimal de 256 chiffres.

Le problème est que la factorisation d'un tel nombre en deux facteurs premiers est un problème de complexité non pas proportionnelle, mais exponentielle.

Il suffit de rajouter quelques chiffres au nombre pour doubler son temps de factorisation.

Or ici, on ajoute donc 512 chiffres... Il faudra le double du double du double . . . du double du double du temps que l'on a mis.
Autrement dit, c'est monstrueux, inenvisageable à une échelle "humaine" pour le moment.

Mais d'un autre côté, la puissance calculatoire de nos ordinateurs suit elle aussi une progression exponentielle selon la loi de Moore (la puissance double tous les deux ans).

Aussi dans quelques années, avec des ordinateurs beaucoup plus puissants, une telle factorisation sera peut-être envisageable.

→ **MyCalcs** profile · by **Ciwtron** » 12 Dec 2009, 18:25

IL y a une formule pour ton "exponentialité"? (Juste pour savoir combien de temps ca prendrait en théorie).

→ **MyCalcs** profile · by **critor** » 12 Dec 2009, 18:36

Ciwtron wrote:IL y a une formule pour ton "exponentialité"? (Juste pour savoir combien de temps ca prendrait en théorie).

Oh, quelque chose comme 4 millions d'années sur un ordinateur seul...
Ou 40 milliers d'années sur une centaine d'ordinateurs travaillant en parallèle...

A ce niveau-là on ne compte plus de toutes façons!

→ **MyCalcs** profile · by **Bisam** » 12 Dec 2009, 18:41

Juste pour éclairer un peu (même si on peut trouver cela expliqué à tous les coins du Net) :

Le principe le plus utilisé pour la cryptographie (c'est-à-dire pour coder des messages) utilise 2 clés : l'une sert à verrouiller et l'autre à déverrouiller.
Ces clés sont en fait constituées de 2 nombres :
- l'un des deux est commun aux 2 clés, c'est le produit de 2 nombres premiers p et q que l'on choisit très grands pour éviter le désagrément que j'évoquerai plus bas.
- l'autre est un entier d ou e qui n'a aucun diviseur commun avec le produit (p-1)*(q-1)

d et e ont été choisis de telle sorte que e*d-1 est multiple de (p-1)*(q-1). e est connu de tous, et d seulement de celui qui veut recevoir des messages cryptés et être le seul à pouvoir les décrypter.

Avec un simple calcul impliquant n=p*q et e, n'importe qui peut crypter un message. Avec un simple calcul impliquant n et d, le destinataire peut le décrypter.
*
Si quelqu'un veut craquer le code, il faut qu'il réussisse à trouver le nombre d. C'est très simple quand on connaît p et q séparément... mais impossible si on ne connaît que n. Il faut donc factoriser n... et le problème c'est qu'on ne dispose d'aucun algorithme performant pour faire ca autrement que par la manière forte : essayer tous les nombres premiers (ou presque).

Conclusion : la seule chose qui manque c'est le temps de calcul car il en faut énormément pour passer en revue tous les nombres premiers.

→ **MyCalcs** profile · by **Marco** » 12 Dec 2009, 19:22

^^
Si tu veux, tout le monde sait comment faire pour décrypter, mais le temps qu'on trouve la clé, l'information cryptée n'est plus utile, c'est pourquoi ce système est l'un des plus sûrs aujourd'hui.
Si quelqu'un trouve le moyen de factoriser rapidement des nombres aussi grands que ceux qu'on utilise pour crypter, il recevra sans aucun doute une médaille Fields ou un prix Abel.

→ **MyCalcs** profile · by **ioraito** » 12 Dec 2009, 19:46

salut à tout je voudrais m'eclairer sur une chose en disant "ordinateur " est ce que vous voulez dire par ça des ordis de notre generation ou autre chose ? , car en pensant à ça on dirait qu'un calcuateur ( ordinateur ultra performant utilisé à des fins scientifique comme celui qui arrive dernierement à simuler une activité cerebrale ) je dirait que quelqun qui à accée à ce materiel pourra le faire (existence de 1 ou 2 maximum par pays )

→ **MyCalcs** profile · by **critor** » 12 Dec 2009, 20:31

ioraito wrote:salut à tout je voudrais m'eclairer sur une chose en disant "ordinateur " est ce que vous voulez dire par ça des ordis de notre generation ou autre chose ? , car en pensant à ça on dirait qu'un calcuateur ( ordinateur ultra performant utilisé à des fins scientifique comme celui qui arrive dernierement à simuler une activité cerebrale ) je dirait que quelqun qui à accée à ce materiel pourra le faire (existence de 1 ou 2 maximum par pays )

Oui on parle d'ordinateurs et non de calculateurs, mais des ordinateurs bien "équipés" toutefois.

Nous n'avons pas accès à des "calculateurs", et n'y aurons probablement jamais accès.

→ **MyCalcs** profile · by **geogeo** » 12 Dec 2009, 23:28

Quoi qu'il en soit même si on avait accès au plus grand super calculateur au monde (Jaguar) on ne pourrait pas casser la clé dans un temps raisonnable !

→ **MyCalcs** profile · by **critor** » 12 Dec 2009, 23:44

geogeo wrote:Quoi qu'il en soit même si on avait accès au plus grand super calculateur au monde (Jaguar) on ne pourrait pas casser la clé dans un temps raisonnable !

C'est ce que je me disais aussi...