Es war einmal, als ich das „In“ auswählte und das „Wie“ eines sehr guten und nützlichen OpenSSL-Pakets studierte, und wie immer tauchte plötzlich eine einfache Idee auf und wie all diese sehr unerwarteten Ideen in Vergessenheit geraten sind.Der trockene Rückstand blieb jedoch erhalten - in OpenSSL wurde ein Fehler beim Multiplizieren einer großen Zahl mit BN_ULONG und eines kleinen Programms zum schrittweisen Extrahieren der Quadratwurzel gefunden. Die Fehlermeldung ging in die Fehlerverfolgung und wurde korrigiert (ich nutze diese Gelegenheit, um mich für meine übermäßige Emotionalität zu entschuldigen, nicht jeden Tag, an dem Sie Fehler in OpenSSL finden), aber das sehr kleine Programm zum Finden der Quadratwurzel ist bitweises Modulo 2 ^ n, wobei n die Anzahl der Bits \ ist Bit Tiefe und machen Sie darauf aufmerksam.Wenn wir den Algorithmus betrachten, zwei Zahlen Bit für Bit in einer Spalte zu multiplizieren, können Sie anhand des Werts der i-Bits der Faktoren, wenn Sie die Übertragung kennen, schnell das Bit des Ergebnisses bestimmen - wenn Sie das Ergebnis kennen und die Verteilung der Bits in den Faktoren annehmen, können Sie diese Bits schnell berechnen. Wie immer geschah nichts Gutes, aber mit der Gleichheit der Faktoren, d.h. Beim Extrahieren der Quadratwurzel kann das entsprechende Bit des Faktors (es ist jetzt eins) schnell erhalten werden.Ob es sich um eine Wurzel handelt oder nicht, wenn n / 2 Bits empfangen werden oder wenn die Zweierpotenz modulo ist, sind die beiden erhaltenen Zahlen die Wurzeln.Kleine Annahmen - wir glauben, dass wir die Wurzel aus einer ungeraden Zahl extrahieren. Wenn die letzten Bits Nullen und ihre gerade Zahl sind, können Sie sie verwerfen.Jetzt ist der Hauptteil natürlich der Code.Zur Verifizierung und zum Testen wurde dieselbe OpenSSL verwendet, um große Primzahlen zu erhalten. Danach wird die Zahl mit BN_mul mit sich selbst multipliziert, und in der Funktion square_root wird die Wurzel zweimal berechnet. Die Berechnungen werden zweimal durchgeführt, da die letzten Bits des Faktors 11 oder 01 für diesen Algorithmus nicht unterscheidbar sind. Zum Speichern von Nummern wird entweder BIGNUM des OpenSSL-Pakets oder Bitset gleicher Länge verwendet.Also Code#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);
}
Der Code ist einfach und ich entschuldige mich in einem Stück - aber da ist der größte Teil der OpenSSL-Dienstprogrammaufrufe, im Root-Berechnungsprogramm beträgt die Auswertung und Berechnung von Bits nur 10 Zeilen, es ist klar, dass DIM eine Dimension ist. p = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
p^2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
0r = 0x1A344C20C2D1C0A95C21151FCDFB5C866A68F40267018DBD14C84003B6CA402D
p2 = 0x02AEAA25AB8538367E9B72A28CBBF36EB8A42E11A66D3283E3230072A9268CE3
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
1r = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
p2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
Die Schlussfolgerung zeigt deutlich, dass sowohl die Zahlen als auch 0r und 1r Quadratwurzeln der Zahl p2 modulo 2 zur Potenz von DIM sind. Jene. 0r * 0r == p2 mod 2 ^ DIM und 1r * 1r == p2 mod 2 ^ DIM. Und außerdem 1r * 1r == p2.Herons Algorithmus ist schnell und es besteht wahrscheinlich keine Notwendigkeit, sich mit Bits zu beschäftigen, aber als Skizze ist das Programm gut.