Érase una vez, mientras elegía el "adentro" y estudiaba el "cómo" de un paquete OpenSSL muy bueno y útil y, como siempre, una idea simple apareció de repente y cómo todas esas ideas tan inesperadas se han hundido en el olvido.Pero el residuo seco permaneció: se encontró un error en OpenSSL al multiplicar un gran número por BN_ULONG y un pequeño programa para extraer la raíz cuadrada bit a bit. El mensaje de error entró en el seguimiento de errores y se corrigió (aprovecho esta oportunidad para disculparme por mi excesiva emocionalidad, no todos los días se encuentran errores en OpenSSL), pero el programa muy pequeño para encontrar la raíz cuadrada es el módulo bit a bit 2 ^ n, donde n es el número de bits \ Profundidad y llamar su atención.Si consideramos el algoritmo de multiplicar dos números bit por bit, en una columna, entonces por el valor de los bits i de los factores, conociendo la transferencia, puede determinar rápidamente el bit del resultado; conociendo el resultado y asumiendo la distribución de bits en los factores, puede calcular rápidamente estos bits. Como siempre, no pasó nada bueno, pero con la igualdad de los factores, es decir al extraer la raíz cuadrada, se puede obtener rápidamente el bit correspondiente del factor (ahora es uno).Obviamente, si se trata de una raíz o no, queda claro cuando se reciben n / 2 bits, o si el módulo es la potencia de dos, entonces los dos números obtenidos serán las raíces.Pequeñas suposiciones: creemos que extraemos la raíz de un número impar. Si los últimos bits son ceros y su número par, puede descartarlos.Ahora, por supuesto, la parte principal es el código.Para verificación y prueba, se tomó el mismo OpenSSL para obtener números primos grandes. Después de eso, el número se multiplica por sí mismo usando BN_mul, y en la función raíz_cuadrada, la raíz se calcula dos veces. Los cálculos se realizan dos veces, ya que los últimos bits del factor 11 o 01 son indistinguibles para este algoritmo. Para almacenar números, se usa BIGNUM del paquete OpenSSL o bitset de la misma longitud.Entonces código#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);
}
El código es simple y pido disculpas en una sola pieza, pero la mayor parte de la parte principal son las llamadas de utilidad OpenSSL, en el programa de cálculo raíz, la evaluación y el cálculo de bits son solo 10 líneas, está claro que DIM es una dimensión. p = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
p^2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
0r = 0x1A344C20C2D1C0A95C21151FCDFB5C866A68F40267018DBD14C84003B6CA402D
p2 = 0x02AEAA25AB8538367E9B72A28CBBF36EB8A42E11A66D3283E3230072A9268CE3
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
1r = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
p2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
La conclusión demuestra claramente que tanto los números como 0r y 1r son raíces cuadradas del número p2 módulo 2 a la potencia de DIM. Aquellos. 0r * 0r == p2 mod 2 ^ DIM y 1r * 1r == p2 mod 2 ^ DIM. Y además, 1r * 1r == p2.El algoritmo de Heron es rápido y probablemente no haya necesidad de quejarse con bits, pero como bosquejo, el programa es bueno.