😚 🍢 🥌 研究比特音 🌪️ 😥 🥦

曾几何时，在选择一个“好”和有用的OpenSSL软件包的“内在”并研究其“方式”时，突然之间出现了一个简单的主意，以及所有这些非常出乎意料的主意如何被遗忘。

但是残留的残留物仍然存在-在OpenSSL中发现了一个错误，将BN_ULONG乘以BN_ULONG，然后用一个小程序逐位提取平方根。错误消息进入bug跟踪并得到纠正（我借此机会为我的过度情绪而道歉，然后，并不是每天都在OpenSSL中发现错误），但是用于查找平方根的非常小的程序是按位模2 ^ n，其中n是位数深度并引起您的注意。

如果我们考虑在一列中将两个数字逐位相乘的算法，然后乘以因子的i位的值，知道传输，则可以快速确定结果的位-知道结果并假设因子中位的分布，就可以快速计算这些位。与往常一样，没有什么好事发生，但在因素相等的情况下，即提取平方根时，可以快速获得因子的对应位（现在为1）。

显然，当接收到n / 2位时，是否为根就变得很清楚，或者如果对2的幂取模，则获得的两个数将为根。

小假设-我们认为我们从奇数中提取根。如果最后一位为零，偶数为零，则可以将其丢弃。

当然，现在的主要部分是代码。

为了进行验证和测试，使用了相同的OpenSSL来获取较大的质数。之后，使用BN_mul将数字乘以自身，然后在square_root函数中，两次计算根。由于因子11或01的最后一位对于该算法是无法区分的，因此计算执行了两次。要存储数字，请使用OpenSSL软件包的BIGNUM或相同长度的位集。

所以代码

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

代码很简单，我向大家道歉-但其中最主要的部分是OpenSSL实用程序调用，在根计算程序中，位的评估和计算仅10行，很明显DIM是一个维度。

   p = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3

p^2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

    0r = 0x1A344C20C2D1C0A95C21151FCDFB5C866A68F40267018DBD14C84003B6CA402D
    p2 = 0x02AEAA25AB8538367E9B72A28CBBF36EB8A42E11A66D3283E3230072A9268CE3
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

    1r = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
    p2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

该结论清楚地表明，数字0r和1r都是p2模2的平方根，而平方2是DIM的幂。那些。0r * 0r == p2 mod 2 ^ DIM和1r * 1r == p2 mod 2 ^ DIM。此外，1r * 1r == p2。

Heron的算法速度很快，可能不需要费神费力，但是作为一个草图，该程序很好。

研究比特音

More articles: