सबसे छोटी संभव RSA निजी और सार्वजनिक कुंजी क्या हैं?
मैं यह समझने की कोशिश कर रहा हूं कि आरएसए सार्वजनिक और निजी चाबियों में सबसे छोटा संभव क्या है। उपयोग करते समय$p = 2, q = 3$एन्क्रिप्शन फ़ंक्शन एन्क्रिप्ट नहीं है। इसलिए मुझे पाने के लिए एक प्राइम शिफ्ट करना होगा$p = 3, q = 3$ और फिर निजी कुंजी है $(9, 3)$ और सार्वजनिक कुंजी भी है $(9, 3)$। मुझे पता है कि यह दो समान अपराधों के गुणनखंड के लिए तुच्छ है और समान निजी और सार्वजनिक कुंजी का होना बुरा है। हालांकि यह सबसे कम (संभव) आरएसए कुंजी जोड़ी है या क्या मैं यहां कुछ याद कर रहा हूं?
जवाब
PKCS # 1v2.2 में RSA की परिभाषा के अनुसार
एक वैध आरएसए निजी कुंजी में , आरएसए मापांक$n$ का उत्पाद है $u$ अलग-अलग अजीब अपराध $r_i$, $i=1$, $2$,…, $u$, कहाँ पे $u\ge2$।
उससे बनता है $n=3\cdot5=15$ सबसे छोटा सार्वजनिक मापांक।
और RSA सार्वजनिक प्रतिपादक $e$ के बीच एक पूर्णांक है $3$ तथा $n–1$ संतोषजनक $\operatorname{GCD}(e,\lambda(n))=1$, कहाँ पे $\lambda(n)=\operatorname{LCM}(r_1–1,\ldots,r_u–1)$
उससे बनता है $e=3$ सबसे छोटा सार्वजनिक प्रतिपादक। $(n,e)=(15,3)$ तब से एक वैध सार्वजनिक कुंजी है $\lambda(15)=4$ तथा $\operatorname{GCD}(3,4)=1$।
RSA निजी घातांक $d$ से कम एक धनात्मक पूर्णांक है $n$ संतोषजनक $e\cdot d\equiv1\pmod{\lambda(n)}\,$।
उससे बनता है $d=1$सबसे छोटा निजी प्रतिपादक। यह से संबंधित है$(n,e)=(15,5)$। उस कुंजी के साथ एन्क्रिप्शन (और डिक्रिप्शन) पहचान है, लेकिन उस के खिलाफ कोई शब्दांकित पर्चे नहीं है।
अगर हम निषेध करते हैं $d=1$, फिर $d=3$ सबसे छोटा निजी प्रतिपादक बन जाता है, मेल खाता है $(n,e)=(15,3)$। अधिक आम तौर पर, आरएसए की विभिन्न परिभाषाएं अलग-अलग निचली सीमाएं उत्पन्न करती हैं। की अनुमति दे$u=1$, $e=1$, और उस नुस्खे को हटा देना $r_i$ अजीब है, बनाता है $(n,e,d)=(2,1,1)$स्वीकार्य है। के लिए FIPS 186-4 , छोटी से छोटी$n$1024-बिट, ए की संभावना है $(\lfloor2^{1023/2}\rfloor+257)\cdot(\lfloor2^{1023/2}\rfloor+2^{412}+431)\,$; सबसे छोटा$e$ है $65537\,$; और सबसे छोटा$d$है बी $2^{512}+1$।
एक: प्रशंसनीय धारणा है कि प्रत्येक के तहत $\lfloor2^{1023/2}\rfloor+256$, $\lfloor2^{1023/2}\rfloor+258$, $\lfloor2^{1023/2}\rfloor+2^{412}+430$ तथा $\lfloor2^{1023/2}\rfloor+2^{412}+432$ कम से कम एक प्रमुख कारक है $2^{100}$, जो मैंने चेक नहीं किया।
B: कुछ मान्य मिलान सार्वजनिक कुंजी $(n,e)$उच्च संभावना के साथ मौजूद है। यह एक को प्रदर्शित करने के लिए एक हल्के दिलचस्प समस्या है।