Get best of the week

الدراسة في نغمات البت

ذات مرة ، أثناء اختيار "الدخول" ودراسة "كيف" لحزمة OpenSSL جيدة ومفيدة للغاية ، وكما هو الحال دائمًا ، ظهرت فجأة فكرة بسيطة وكيف أن كل هذه الأفكار غير المتوقعة قد غرقت في النسيان.

ولكن بقيت البقايا الجافة - تم العثور على خطأ في OpenSSL ، في ضرب عدد كبير في BN_ULONG وبرنامج صغير لاستخراج الجذر التربيعي بتة. دخلت رسالة الخطأ في تتبع الأخطاء وتم تصحيحها (أغتنم هذه الفرصة لأعتذر عن الانفعالات المفرطة التي تواجهني ، ليس كل يوم تجد أخطاء في OpenSSL) ، ولكن البرنامج الصغير جدًا للعثور على الجذر التربيعي هو bitwise modulo 2 ^ n ، حيث n هو عدد البتات \ عمق قليلا وجذب انتباهكم.

إذا أخذنا في الاعتبار خوارزمية ضرب رقمين بتًا ، في عمود ، ثم بقيمة البتات من العوامل ، ومعرفة النقل ، يمكنك تحديد بت النتيجة بسرعة - معرفة النتيجة وافتراض توزيع البتات في العوامل ، يمكنك حساب هذه البتات بسرعة. كما هو الحال دائمًا ، لم يحدث شيء جيد ، ولكن مع مساواة العوامل ، أي عند استخراج الجذر التربيعي ، يمكن الحصول بسرعة على الجزء المقابل من العامل (وهو الآن واحد). من

الواضح ، ما إذا كان الجذر أم لا يصبح واضحًا عند تلقي بتات n / 2 ، أو إذا كان modulo قوة اثنين ، فسيكون الرقمان الذي تم الحصول عليهما هما الجذور.

افتراضات صغيرة - نعتقد أننا نستخرج الجذر من عدد فردي. إذا كانت البتات الأخيرة عبارة عن أصفار ورقم زوجي ، فيمكنك التخلص منها.

الآن بالطبع الجزء الرئيسي هو الرمز.

للتحقق والاختبار ، تم أخذ نفس OpenSSL للحصول على أعداد أولية كبيرة. بعد ذلك ، يتم ضرب الرقم في حد ذاته باستخدام BN_mul ، وفي دالة square_root ، يتم حساب الجذر مرتين. يتم إجراء الحسابات مرتين ، حيث لا يمكن تمييز الأجزاء الأخيرة من العامل 11 أو 01 لهذه الخوارزمية. لتخزين الأرقام ، يتم استخدام إما BIGNUM لحزمة OpenSSL أو بتات بنفس الطول.

لذا كود

#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

يوضح الاستنتاج بوضوح أن كلاً من الأرقام و 0 r و 1 r هي الجذور التربيعية لعدد 2 p2 modulo إلى قوة DIM. أولئك. 0r * 0r == p2 mod 2 ^ DIM و 1r * 1r == p2 mod 2 ^ DIM. بالإضافة إلى ذلك ، 1r * 1r == p2.

خوارزمية هيرون سريعة ، وربما لا تكون هناك حاجة للتشويش بالقطع ، ولكن كرسم تخطيطي ، البرنامج جيد.

More articles:


All Articles