Codage RSA - Page 1

Bonjour!. Je pense présentement à concevoir un programme qui encoderait/décoderait des fichiers textes selon la méthode RSA (la même qui est utilisée sur les sites sécurisés), mais je bute sur le traitement des grands nombres impliqués là-dedans. Ces nombres sont de l'ordre de 1056^823, et ne rentrent pas dans un double double... que faire?

Il faut utiliser un algorithme spécialisé pour calculer les puissances modulo N. Il y a des implémentations sous GPL, probablement aussi certaines sous licence BSD, que tu peux regarder. N'importe quelle librairie de cryptographie sérieuse gère le RSA de nos jours (depuis que le brevet a expiré).

au hasard libtomcrypt qui est du domaine public (pas GPL, pas bsd, rien)

c'est assez éducatif en plus. L'idée de base c'est la multiplication de Montgomery, la multiplication naïve est inutilisable. (je l'ai codé, pour voir, et... hem nan, après deux jours de calcul sur un core2, j'en ai déduit qu'il fallait une optim plus sioux)

et [u]/![/u] c'est ULTRA RARE de coder un texte complet en RSA, car ce qu'on obtient, ce sont des grands nombres, et ça demande énormément de calculs, et c'est pas facile à stocker. L'approche de base est de coder en RSA une clé de chiffrement et d'utiliser ensuite un chiffrement symétrique genre AES.

Faut voir aussi comment on code les données avant de les soumettre à la moulinette RSA, en général ça suffit pas de prendre un simple bloc d'octet et de l'élever à la puissance modulo N, car on peut casser le codage de cette manière. Il vaut mieux suivre les méthodes décrites dans la spec PKCS#1 qui définit des algos de hachage de texte avant l'exponentiation. Ca s'appelle RSAES-OAEP.

(mais si c'est un algo "pour voir" pas la peine de t'embêter)

PKCS1v2: http://www.rsa.com/rsalabs/node.asp?id=2125 (Norme au format texte)
TomCrypt: http://libtom.org/?page=features&whatfile=crypt

En fait, c'est plutôt "pour voir", comme tu dis... l'idée ici ce n'est pas d'encoder tout le texte d'une frappe, mais plutôt 2 ou 3 caractères à la fois...

oki

(mais même)

fais des tests et dis moi, ça m'intéresse.
Je pense que le temps de calcul du cryptage sera très important. A voir.

KillerX (./1) :
Ces nombres sont de l'ordre de 1056^823, et ne rentrent pas dans un double double... que faire?

Encore heureux, sinon ton message complet tiendrait sur quelques octets, et tu aurais aussi inventé un algo de compression super efficace
Plus sérieusement, faut que tu manges la théorie derrière. RSA c'est pas de la bidouille, c'est des mathématiques, et pas des plus simples.

On ne peut pas utiliser des flottants pour faire ce genre d'opérations sur les entiers, d'ailleurs, les arrondis détruisent toute l'information!

(oué, en plus )

Côté maths, c'est pas vraiment ça le problème, en fait on voit la théorie nécessaire en cours de math... j'aimerais juste pousser ça un peu plus loin, c'est tout... en fait, je suis encore à l'étape de la conception; je n'ai pas encore codé une seule ligne, je suis plutôt occupé à penser aux différents problèmes que je pourrais rencontrer et à la facon dont je vais les résoudre...

oki

tiens nous au courant si tu bloques.

tu comptes le programmer en quel langage?

>tu comptes le programmer en quel langage?

en C... c'est celui où je suis le plus à l'aise...

Je vous tiens au courant, je vais sûrement commencer le code lorsque jaurai du temps cette semaine... Je vous ferai savoir si j'ai des questions

(en Java, il y a (de base) la classe BigInteger qui permet d'avoir des entiers de n'importe quelle taille).

oui, c'est ça qu'il doit recoder en C (et que j'ai fait aussi)

Les opérations de base fonctionnent, mais sont très lentes pour faire du RSA. Surtout la division, qui se fait par dichotomie, et qui est nécessaire pour chaque opération modulaire.
Naïvement ça passe pas.

Je vais utiliser la multiplication modulaire de Montgomery pour accélérer l'exponentiation modulaire, mais je l'ai pas encore codée.

Perso, je comptais plutôt "casser" l'opération en plusieurs parties, assez petites pour être calculées...
ex: 10 mod 3 => 5*2 mod 3 => (5 mod 3) * (2 mod 3) => (2*2) mod 3 = 1
ce qui est bien égal à 10 mod 3... Peut-être que je me trompe, mais à première vue, ça semble marcher.

De toute façon, je ne compte pas coder en RSA 128 bits; je vais plutôt garder des nombres pas trop gros...

et pour trouver que 10=5*2 tu fais comment? une division? paf

les nombres que tu vas "moduler" sont des puissances: c^e, pour coder, e=65537 en général, et pour décoder, e=nombre imbitable du même ordre de grandeur que le modulo

pour ta culture, "des gens" ont réussi à factoriser un nombre premier de 640 bits http://www.rsa.com/rsalabs/node.asp?id=2964

donc il est recommandé pour la sécurité de ne pas employer de nombres ayant moins de 1024 bits. le mouvement est en train d'aller vers les 2048 bits.
Donc si tu codes pour apprendre, commence par des petits nombres, mais intéresse toi aussi à la méthode de calcul pour les "gros" nombres