RSA में e और d का सही व्युत्क्रम: lcm(p-1,q-1) से जाँच

PyCryptodome में RSA कुंजियों की जाँच सही तरह करें: phi के बजाय Carmichael lambda (lcm(p-1,q-1)) पर e·d == 1 सत्यापित करें। कारण, उदाहरण कोड और व्यावहारिक टिप्स।

PyCryptodome में RSA कुंजी-जनन पहली नज़र में असंगत लग सकता है, खासकर जब आप सार्वजनिक और निजी घातांकों के बीच modular inverse संबंध को परखने की कोशिश करते हैं। हैरानी तब होती है जब कुछ कुंजियों के लिए ऑयलर के टॉशेंट के खिलाफ जाँच गैर-शून्य शेषफल देती है—हालाँकि एन्क्रिप्शन और डिक्रिप्शन बिना किसी समस्या के काम करते रहते हैं।

समस्या का पुनरुत्पादन

नीचे दिया गया छोटा सा कोड Crypto.PublicKey.RSA और gmpy2 का उपयोग करके (e · d − 1) को (p − 1)(q − 1) से भाग देने पर आने वाला शेषफल निकालता है। आम धारणा यह है कि यह शेषफल हमेशा शून्य होना चाहिए—यहीं से भ्रम पैदा होता है।

from Crypto.PublicKey import RSA
import gmpy2 as gp
z = gp.mpz(0)
o = gp.mpz(1)
kpair = RSA.generate(1024)
p_val = gp.mpz(kpair.p)
q_val = gp.mpz(kpair.q)
n_mod = gp.mpz(kpair.n)
d_sec = gp.mpz(kpair.d)
e_pub = gp.mpz(kpair.e)
phi_mod = gp.mul(gp.sub(p_val, o), gp.sub(q_val, o))
quot, rem = gp.t_divmod(gp.sub(gp.mul(e_pub, d_sec), o), phi_mod)
print("remainder:", rem)
assert rem == z

वास्तव में क्या हो रहा है

समस्या की जड़ यह मान लेना है कि e और d, n के ऑयलर टॉशेंट (phi) के मॉड्यूलो में परस्पर गुणात्मक व्युत्क्रम हैं। PyCryptodome में d को e का व्युत्क्रम n के Carmichael के lambda फ़ंक्शन के सापेक्ष बनाया जाता है, न कि ऑयलर के टॉशेंट के सापेक्ष। दोनों ही विकल्प RSA के लिए सही हैं, लेकिन Carmichael का lambda लेने से निजी घातांक कुछ बिट छोटा हो जाता है और इसलिए थोड़ा अधिक कुशल रहता है। यही तरीका PyCryptodome और कई अन्य इम्प्लीमेंटेशन अपनाते हैं।

जब RSA का मापांक दो अभाज्यों p और q से बना हो, तो Carmichael का lambda lcm(p − 1, q − 1) के रूप में निकाला जाता है। इसे पाना (p − 1)(q − 1) के गुणन जितना ही सरल है, लेकिन इससे e और d के लिए किस संगति का पालन होना चाहिए, यह बदल जाता है।

सत्यापन को सही करना

कुंजी को ठीक उसी तरह जाँचने के लिए जैसा PyCryptodome उसे परिभाषित करता है, p − 1 और q − 1 का लघुत्तम समापवर्त्य निकालें और उसी मान के मॉड्यूलो में व्युत्क्रम संबंध की जाँच करें।

from Crypto.PublicKey import RSA
import gmpy2 as gp
import math
z = gp.mpz(0)
o = gp.mpz(1)
kpair = RSA.generate(1024)
p_val = gp.mpz(kpair.p)
q_val = gp.mpz(kpair.q)
d_sec = gp.mpz(kpair.d)
e_pub = gp.mpz(kpair.e)
lam_mod = math.lcm(int(p_val - o), int(q_val - o))
quo2, rem2 = gp.t_divmod(gp.sub(gp.mul(e_pub, d_sec), o), gp.mpz(lam_mod))
print("remainder_lambda:", rem2)
assert rem2 == z

चाहें तो आप यही शर्त और सीधे रूप में भी लिख सकते हैं:

assert (int(e_pub) * int(d_sec)) % lam_mod == 1

यह क्यों महत्वपूर्ण है

जब आप क्रिप्टोग्राफ़िक कोड का ऑडिट करते हैं या उसमें जाँच जोड़ते हैं, तो अक्सर ऐसी कसौटियाँ लगा दी जाती हैं जो व्युत्क्रम संबंध के लिए ऑयलर के टॉशेंट को ही मानक मॉड्यूलस मानती हैं। यह मानना उन लाइब्रेरीज़ के लिए झूठे अलर्ट पैदा करेगा जो Carmichael का lambda उपयोग करती हैं—हालाँकि कुंजियाँ वैध होती हैं और एल्गोरिद्म ठीक से काम करते हैं। कौन‑सा मॉड्यूलस लक्षित है यह समझना स्वस्थ कुंजियों को गलत तरीके से असंगत बताने से रोकता है और आपकी जाँच को लाइब्रेरी के डिज़ाइन के अनुरूप रखता है।

मुख्य बातें

यदि आप PyCryptodome की RSA कुंजियों का सत्यापन करते हैं, तो हर कुंजी के लिए (e · d − 1) mod (p − 1)(q − 1) के शून्य होने की अपेक्षा न करें। इसके बजाय जाँच के लिए मॉड्यूलस के रूप में lcm(p − 1, q − 1) लें। यह उसी परिभाषा से मेल खाता है जिससे लाइब्रेरी निजी घातांक तय करती है, अनावश्यक assertion विफलताओं से बचाता है, और उस आम प्रथा को दर्शाता है जिसमें d का आकार थोड़ा घटता है, जबकि RSA की शुद्धता अपरिवर्तित रहती है।