🤰 👐🏻 📃 Estudar em tons de bits 👩🏽‍🤝‍👩🏻 🌱 🤵🏽

Era uma vez, enquanto selecionava o "in" e estudava o "como" de um pacote OpenSSL muito bom e útil e, como sempre inesperadamente, surgiu uma idéia simples e como todas essas idéias inesperadas desapareceram.

Mas o resíduo seco permaneceu - um erro foi encontrado no OpenSSL, ao multiplicar um número grande por BN_ULONG e um pequeno programa para extrair a raiz quadrada pouco a pouco. A mensagem de erro entrou no rastreamento de bugs e foi corrigida (aproveito a oportunidade para me desculpar pela minha emocionalidade excessiva, não todos os dias que você encontra erros no OpenSSL), mas o programa muito pequeno para encontrar a raiz quadrada é o módulo bit a bit 2 ^ n, em que n é o número de bits \ profundidade e traga à sua atenção.

Se considerarmos o algoritmo de multiplicar dois números bit por bit, em uma coluna, pelo valor dos i-bits dos fatores, conhecendo a transferência, você poderá determinar rapidamente o bit do resultado - conhecendo o resultado e assumindo a distribuição dos bits nos fatores, poderá calcular rapidamente esses bits. Como sempre, nada de bom aconteceu, mas com a igualdade dos fatores, ou seja, ao extrair a raiz quadrada, o bit correspondente do fator (agora é um) pode ser obtido rapidamente.

Obviamente, se é uma raiz ou não, fica claro quando n / 2 bits são recebidos, ou se modula a potência de dois, então os dois números obtidos serão as raízes.

Pequenas suposições - acreditamos que extraímos a raiz de um número ímpar. Se os últimos bits são zeros e seu número par, você pode descartá-los.

Agora, claro, a parte principal é o código.

Para verificação e teste, o mesmo OpenSSL foi utilizado para obter grandes números primos. Depois disso, o número é multiplicado por si próprio usando BN_mul e, na função square_root, a raiz é calculada duas vezes. Os cálculos são realizados duas vezes, pois os últimos bits do fator 11 ou 01 são indistinguíveis para esse algoritmo. Para armazenar números, é usado o BIGNUM do pacote OpenSSL ou o conjunto de bits do mesmo comprimento.

Então codifique

#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);
}

O código é simples e peço desculpas de uma só vez - mas a maior parte da parte principal são chamadas de utilitário OpenSSL, no programa de cálculo raiz, a avaliação e o cálculo de bits são apenas 10 linhas, é claro que DIM é uma dimensão.

   p = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3

p^2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

    0r = 0x1A344C20C2D1C0A95C21151FCDFB5C866A68F40267018DBD14C84003B6CA402D
    p2 = 0x02AEAA25AB8538367E9B72A28CBBF36EB8A42E11A66D3283E3230072A9268CE3
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

    1r = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
    p2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

a conclusão demonstra claramente que os números e 0r e 1r são raízes quadradas do número p2 módulo 2 à potência do DIM. Essa. 0r * 0r == p2 mod 2 ^ DIM e 1r * 1r == p2 mod 2 ^ DIM. Além disso, 1r * 1r == p2.

O algoritmo de Heron é rápido e provavelmente não há necessidade de mexer com bits, mas como um esboço, o programa é bom.

Estudar em tons de bits

More articles: