Il était une fois, tout en choisissant le «in» et en étudiant le «comment» d'un package OpenSSL très bon et utile et, comme toujours, une idée simple est soudainement apparue et comment toutes ces idées très inattendues sont tombées dans l'oubli.Mais le résidu sec est resté - une erreur a été trouvée dans OpenSSL, en multipliant un grand nombre par BN_ULONG et un petit programme pour extraire la racine carrée bit par bit. Le message d'erreur est entré dans le suivi des bogues et a été corrigé (j'en profite pour m'excuser pour mon émotivité excessive alors, pas tous les jours vous trouvez des erreurs dans OpenSSL), mais le très petit programme pour trouver la racine carrée est bituleux modulo 2 ^ n, où n est le nombre de bits \ peu de profondeur et porter à votre attention.Si nous considérons l'algorithme de multiplication de deux nombres bit par bit, dans une colonne, puis par la valeur des i-bits des facteurs, connaissant le transfert, vous pouvez rapidement déterminer le bit du résultat - connaissant le résultat et supposant la distribution des bits dans les facteurs, vous pouvez rapidement calculer ces bits. Comme toujours, rien de bon ne s'est passé, mais avec l'égalité des facteurs, c'est-à-dire lors de l'extraction de la racine carrée, le bit correspondant du facteur (il est maintenant un) peut être obtenu rapidement.Évidemment, qu'il s'agisse d'une racine ou non devient clair lorsque n / 2 bits sont reçus, ou si modulo la puissance de deux, alors les deux nombres obtenus seront les racines.Petites hypothèses - nous pensons que nous extrayons la racine d'un nombre impair. Si les derniers bits sont des zéros et leur nombre pair, vous pouvez les supprimer.Maintenant, bien sûr, la partie principale est le code.Pour la vérification et les tests, le même OpenSSL a été utilisé pour obtenir de grands nombres premiers. Après cela, le nombre est multiplié par lui-même à l'aide de BN_mul, et dans la fonction square_root, la racine est calculée deux fois. Les calculs sont effectués deux fois, car les derniers bits du facteur 11 ou 01 sont indiscernables pour cet algorithme. Pour stocker des nombres, BIGNUM du package OpenSSL ou un ensemble de bits de même longueur sont utilisés.Alors codez#include <bitset>
#include <stdio.h>
#include <openssl/rsa.h>
#include <openssl/bn.h>
using namespace std;
#define DIM 512
int ret = 0;
RSA *r = NULL;
BIGNUM *bne = NULL;
BIO *bp_public = NULL, *bp_private = NULL;
int bits = DIM;
unsigned long e = RSA_F4;
bool generate_key() {
r = RSA_new();
ret = RSA_generate_key_ex(r, bits, bne, NULL);
return (ret );
}
bitset<DIM> square_root(bitset<DIM> key, int prim_1) {
bitset<DIM> prim;
int carry = prim_1;
int i, j, ie;
prim[0] = 1;
prim[1] = prim_1;
ie = DIM / 2;
for (i = 2; i < ie; i++) {
for (j = 1; j < i; j++)
carry = carry + (int) (prim[j] * prim[i - j]);
bool i1 = i & 1;
int q2 = (carry / 2) & 1;
int key1 = (int) key[i + 1];
if (!i1 && q2 != key1)
prim[i] = 1;
if (!i1 && q2 == key1)
prim[i] = 0;
if (i1 && q2 == key1)
prim[i] = prim[(i + 1) / 2];
if (i1 && q2 != key1)
prim[i] = 1 - (int) prim[(i + 1) / 2];
carry += 2 * (int) prim[i];
carry /= 2;
}
return prim;
}
int main() {
bitset<DIM> bit0_sqrt(0);
bitset<DIM> bit1_sqrt(0);
bitset<DIM> bit_p2(1);
bne = BN_new();
ret = BN_set_word(bne, e);
char *pc, *qc, *rc;
if (generate_key() == 1) {
BIGNUM *rez = NULL;
BIGNUM *p2 = NULL;
BIGNUM *tmp = NULL;
const BIGNUM *n = NULL;
const BIGNUM *e = NULL;
const BIGNUM *d = NULL;
const BIGNUM *p = NULL;
const BIGNUM *q = NULL;
RSA_get0_key(r, &n, &e, &d);
RSA_get0_factors(r, &p, &q);
pc = BN_bn2hex(p);
printf(" p = 0x%s\n", pc);
p2 = BN_new();
tmp = BN_new();
BN_CTX *ctx;
ctx = BN_CTX_new();
BN_CTX_start(ctx);
BN_mul(p2, p, p, ctx);
pc = BN_bn2hex(p2);
printf("p^2 = 0x%s\n", pc);
bit_p2 = 0;
for (int i = 0; i < BN_num_bits(p2); i++)
if (BN_is_bit_set(p2, i))
bit_p2[i] = 1;
rez = BN_new();
bit0_sqrt = square_root(bit_p2, 0);
for (int i = 0; i < DIM; i++)
if (bit0_sqrt[i])
BN_set_bit(rez, i);
else
BN_clear_bit(rez, i);
rc = BN_bn2hex(rez);
printf(" 0r = 0x%s\n", rc);
BN_sqr(tmp, rez, ctx);
rc = BN_bn2hex(tmp);
printf(" p2 = 0x%s\n", rc);
bit1_sqrt = square_root(bit_p2, 1);
for (int i = 0; i < DIM; i++)
if (bit1_sqrt[i])
BN_set_bit(rez, i);
else
BN_clear_bit(rez, i);
rc = BN_bn2hex(rez);
printf(" 1r = 0x%s\n", rc);
BN_sqr(tmp, rez, ctx);
rc = BN_bn2hex(tmp);
printf(" p2 = 0x%s\n", rc);
}
BIO_free_all(bp_public);
BIO_free_all(bp_private);
RSA_free(r);
BN_free(bne);
}
Le code est simple et je m'excuse en un seul morceau - mais la plupart de la partie principale est les appels de l'utilitaire OpenSSL, dans le programme de calcul racine, l'évaluation et le calcul des bits ne sont que de 10 lignes, il est clair que DIM est une dimension. p = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
p^2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
0r = 0x1A344C20C2D1C0A95C21151FCDFB5C866A68F40267018DBD14C84003B6CA402D
p2 = 0x02AEAA25AB8538367E9B72A28CBBF36EB8A42E11A66D3283E3230072A9268CE3
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
1r = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
p2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
la conclusion démontre clairement que les nombres et 0r et 1r sont les racines carrées du nombre p2 modulo 2 à la puissance de DIM. Ceux. 0r * 0r == p2 mod 2 ^ DIM et 1r * 1r == p2 mod 2 ^ DIM. Et en plus, 1r * 1r == p2.L'algorithme de Heron est rapide et il n'est probablement pas nécessaire de s'occuper des bits, mais en tant que croquis, le programme est bon.