Get best of the week

Study in bit tones

Once upon a time, while picking the “in” and studying the “how” of a very good and useful OpenSSL package and, as always, one simple idea suddenly appeared and how all such very unexpected ideas have sunk into oblivion.

But the dry residue remained - an error was found in OpenSSL, in multiplying a large number by BN_ULONG and a small square root program bit by bit. The error message went into bug tracking and was corrected (I take this opportunity to apologize for my excessive emotionality then, not every day you find errors in OpenSSL), but the very small program for finding the square root is bitwise modulo 2 ^ n, where n is the number of bits \ bit depth and bring to your attention.

If we consider the algorithm of multiplying two numbers bit by bit, in a column, then by the value of the i-bits of the factors, knowing the transfer, you can quickly determine the bit of the result - knowing the result and assuming the distribution of bits in the factors, you can quickly calculate these bits. As always, nothing good happened, but with the equality of the factors, i.e. when extracting the square root, the corresponding bit of the factor (it is now one) can be quickly obtained.

Obviously, whether it is a root or not becomes clear when n / 2 bits are received, or if modulo the power of two, then the two numbers obtained will be the roots.

Small assumptions - we believe that we extract the root from an odd number. If the last bits are zeros and their even number, then you can discard them.

Now of course the main part is the code.

For verification and testing, the same OpenSSL was taken to obtain large prime numbers. After that, the number is multiplied by itself using BN_mul, and in the square_root function, the root is calculated twice. The calculations are performed twice, since the last bits of the factor 11 or 01 are indistinguishable for this algorithm. To store numbers, either BIGNUM of the OpenSSL package or bitset of the same length are used.

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

The code is simple and I apologize in one piece - but there most of the main part is the OpenSSL utility calls, in the root calculation program, the evaluation and calculation of bits is only 10 lines, it is clear that DIM is a dimension.

   p = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3

p^2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

    0r = 0x1A344C20C2D1C0A95C21151FCDFB5C866A68F40267018DBD14C84003B6CA402D
    p2 = 0x02AEAA25AB8538367E9B72A28CBBF36EB8A42E11A66D3283E3230072A9268CE3
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

    1r = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
    p2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

the conclusion clearly demonstrates that both numbers and 0r and 1r are square roots of the number p2 modulo 2 to the power of DIM. Those. 0r * 0r == p2 mod 2 ^ DIM and 1r * 1r == p2 mod 2 ^ DIM. And besides, 1r * 1r == p2.

Heron's algorithm is fast and there is probably no need for fussing with bits, but as a sketch, the program is good.

More articles:


All Articles