👩‍🔬 🦉 📩 बिट टन में अध्ययन 👩‍👧‍👦 🎎 🖥️

एक बार, "इन" उठाते समय और एक बहुत अच्छे और उपयोगी ओपनएसएसएल पैकेज के "कैसे" का अध्ययन करते हुए, और हमेशा की तरह, एक सरल विचार अचानक सामने आया और इस तरह के सभी बहुत ही अप्रत्याशित विचार गुमनामी में डूब गए।

लेकिन शुष्क अवशेष बने रहे - OpenSSL में एक त्रुटि पाई गई, बड़ी संख्या में BN_ULONG और एक छोटे से वर्गमूल प्रोग्राम को बिट द्वारा गुणा करने में। त्रुटि संदेश बग ट्रैकिंग में चला गया और ठीक कर दिया गया (मैं अपनी अत्यधिक भावुकता के लिए माफी मांगने का यह अवसर लेता हूं, फिर हर दिन आपको ओपनएसएसएल में त्रुटियां नहीं मिलती हैं), लेकिन वर्गमूल को खोजने के लिए बहुत छोटा प्रोग्राम बिटवाइज़ मोडुलो 2 है - जहां बिट्स की संख्या \ n है। थोड़ी गहराई और अपने ध्यान में लाएं।

यदि हम एक कॉलम में, बिट संख्याओं को बिट से गुणा करने के एल्गोरिथ्म पर विचार करते हैं, तो कारकों के आई-बिट्स के मूल्य से, स्थानांतरण को जानकर, आप जल्दी से परिणाम के बिट को निर्धारित कर सकते हैं - परिणाम जानने और कारकों में बिट्स के वितरण का अनुमान लगाते हुए, आप इन बिट्स की जल्दी से गणना कर सकते हैं। हमेशा की तरह, कुछ भी अच्छा नहीं हुआ, लेकिन कारकों की समानता के साथ, अर्थात्। जब वर्गमूल निकालते हैं, तो कारक का संगत बिट (यह अब एक है) जल्दी से प्राप्त किया जा सकता है।

जाहिर है, जब n / 2 बिट प्राप्त होता है, तो यह एक जड़ है या स्पष्ट नहीं होता है, या यदि दो की शक्ति को मापता है, तो प्राप्त दो संख्याएं जड़ें होंगी।

छोटी धारणाएँ - हम मानते हैं कि हम विषम संख्या से जड़ को निकालते हैं। यदि अंतिम बिट्स शून्य हैं और उनकी सम संख्या है, तो आप उन्हें छोड़ सकते हैं।

अब निश्चित रूप से मुख्य भाग कोड है।

सत्यापन और परीक्षण के लिए, बड़े प्राइम नंबर प्राप्त करने के लिए एक ही ओपनएसएसएल लिया गया था। उसके बाद, बीएन_मूल का उपयोग करके संख्या को खुद से गुणा किया जाता है, और स्क्वायर_रॉट फ़ंक्शन में, रूट की दो बार गणना की जाती है। गणना दो बार की जाती है, क्योंकि कारक 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);
}

कोड सरल है और मैं एक टुकड़े में माफी मांगता हूं - लेकिन मुख्य भाग का अधिकांश भाग ओपनएसएसएल उपयोगिता कॉल है, रूट गणना कार्यक्रम में, बिट्स का मूल्यांकन और गणना केवल 10 लाइनें हैं, यह स्पष्ट है कि डीआईएम एक आयाम है।

   p = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3

p^2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

    0r = 0x1A344C20C2D1C0A95C21151FCDFB5C866A68F40267018DBD14C84003B6CA402D
    p2 = 0x02AEAA25AB8538367E9B72A28CBBF36EB8A42E11A66D3283E3230072A9268CE3
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

    1r = 0xE5CBB3DF3D2E3F56A3DEEAE03204A37995970BFD98FE7242EB37BFFC4935BFD3
    p2 = 0xCE4611E425E1B6E3C6594862F0C53A61E3D2460CD86A1709B992806B3B920C89
F2F33861A38225ABFB4A95E65852BEB5930F7968120D65F039A83417531A87E9

निष्कर्ष स्पष्ट रूप से दर्शाता है कि दोनों संख्याएँ और 0r और 1r, संख्या 2 के modulo 2 के वर्गमूल हैं DIM की शक्ति के लिए। उन। 0r * 0r == P2 mod 2 ^ DIM और 1r * 1r == P2 mod 2 ^ DIM। और इसके अलावा, 1r * 1r == P2।

बगुला का एल्गोरिथ्म तेज है और बिट्स के साथ उपद्रव की आवश्यकता नहीं है, लेकिन एक स्केच के रूप में, कार्यक्रम अच्छा है।

बिट टन में अध्ययन

More articles: