Sekali waktu, sambil memilih "dalam" dan mempelajari "bagaimana" dari paket OpenSSL yang sangat baik dan berguna dan, seperti biasa, satu ide sederhana tiba-tiba muncul dan bagaimana semua ide yang sangat tak terduga itu telah tenggelam terlupakan.Tetapi residu kering tetap ada - kesalahan ditemukan di OpenSSL, dalam mengalikan sejumlah besar dengan BN_ULONG dan program kecil untuk mengekstrak akar kuadrat sedikit demi sedikit. Pesan kesalahan masuk ke pelacakan bug dan diperbaiki (saya mengambil kesempatan ini untuk meminta maaf atas emosi berlebihan saya, kemudian, tidak setiap hari Anda menemukan kesalahan dalam OpenSSL), tetapi program yang sangat kecil untuk menemukan akar kuadrat adalah modulo 2 ^ n, di mana n adalah jumlah bit \ Kedalaman dan bawa perhatian Anda.Jika kita mempertimbangkan algoritma mengalikan dua angka sedikit demi sedikit, dalam sebuah kolom, maka dengan nilai i-bit faktor, mengetahui transfer, Anda dapat dengan cepat menentukan bit hasilnya - mengetahui hasilnya dan mengasumsikan distribusi bit dalam faktor, Anda dapat dengan cepat menghitung bit ini. Seperti biasa, tidak ada hal baik yang terjadi, tetapi dengan persamaan faktor, yaitu ketika mengekstraksi akar kuadrat, bit faktor yang sesuai (sekarang satu) dapat dengan cepat diperoleh.Tentu saja, apakah itu root atau tidak menjadi jelas ketika n / 2 bit diterima, atau jika modulo kekuatan dua, maka dua angka yang diperoleh akan menjadi root.Asumsi kecil - kami percaya bahwa kami mengekstrak root dari angka ganjil. Jika bit terakhir adalah nol dan jumlahnya genap, maka Anda dapat membuangnya.Sekarang tentu saja bagian utama adalah kode.Untuk verifikasi dan pengujian, OpenSSL yang sama diambil untuk mendapatkan bilangan prima yang besar. Setelah itu, angka dikalikan dengan sendirinya menggunakan BN_mul, dan dalam fungsi square_root, root dihitung dua kali. Perhitungan dilakukan dua kali, karena bit terakhir dari faktor 11 atau 01 tidak dapat dibedakan untuk algoritma ini. Untuk menyimpan angka, digunakan BIGNUM dari paket OpenSSL atau bitet dengan panjang yang sama.Jadi kode#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);
}
Kode sederhana dan saya minta maaf dalam keadaan utuh - tetapi ada sebagian besar bagian utama adalah panggilan utilitas OpenSSL, dalam program perhitungan root, evaluasi dan perhitungan bit hanya 10 baris, jelas bahwa DIM adalah dimensi. p = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
p^2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
0r = 0x1A344C20C2D1C0A95C21151FCDFB5C866A68F40267018DBD14C84003B6CA402D
p2 = 0x02AEAA25AB8538367E9B72A28CBBF36EB8A42E11A66D3283E3230072A9268CE3
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
1r = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
p2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9
kesimpulannya dengan jelas menunjukkan bahwa angka dan 0r dan 1r adalah akar kuadrat dari angka p2 modulo 2 dengan kekuatan DIM. Itu 0r * 0r == p2 mod 2 ^ DIM dan 1r * 1r == p2 mod 2 ^ DIM. Dan selain itu, 1r * 1r == p2.Algoritma heron cepat dan mungkin tidak perlu repot dengan bit, tetapi sebagai sketsa, programnya bagus.