नैपसैक एल्गोरिद्म क्रिप्टोग्राफी में (Knapsack Algorithm in Cryptography)

परिचय:

Knapsack Algorithm क्रिप्टोग्राफी में एक प्रारंभिक Public Key Cryptosystem है जिसे 1978 में Ralph Merkle और Martin Hellman ने विकसित किया था। इसे Merkle–Hellman Knapsack Cryptosystem के नाम से भी जाना जाता है।

यह एल्गोरिद्म Subset Sum Problem पर आधारित है, जो गणनात्मक रूप से कठिन (NP-complete) समस्या है। इस वजह से इसे क्रिप्टोग्राफी में सुरक्षा के लिए उपयोग किया गया।

नैपसैक समस्या (Knapsack Problem):

Knapsack समस्या एक गणितीय समस्या है जिसमें कुछ वस्तुएँ (Items) और एक क्षमता (Capacity) दी जाती है। हमें तय करना होता है कि किन वस्तुओं को चुना जाए ताकि कुल भार क्षमता से अधिक न हो और कुल मूल्य अधिकतम हो।

Cryptography में इसका एक विशेष रूप उपयोग किया जाता है — Subset Sum Problem, जिसमें यह तय किया जाता है कि क्या किसी दिए गए संख्याओं के subset का योग किसी विशिष्ट संख्या के बराबर है या नहीं।

Subset Sum Problem का उदाहरण:

मान लें संख्याएँ: [2, 3, 7, 8, 10] क्या कोई subset ऐसा है जिसका योग 11 है? उत्तर: हाँ → {3, 8}

Knapsack Cryptosystem का मूल सिद्धांत:

Merkle–Hellman Cryptosystem इस समस्या के एक विशेष प्रकार Super-Increasing Sequence का उपयोग करता है। इसमें प्रत्येक अगली संख्या, पिछली सभी संख्याओं के योग से बड़ी होती है।

उदाहरण के लिए: [2, 3, 7, 14, 30, 57, 120] यह Super-Increasing Sequence है क्योंकि:

• 3 > 2
• 7 > 2 + 3
• 14 > 2 + 3 + 7
• 30 > 2 + 3 + 7 + 14, आदि।

---

Knapsack Cryptosystem की प्रक्रिया:

इस प्रणाली में तीन चरण होते हैं:

1. Key Generation (कुंजी निर्माण)
2. Encryption (एन्क्रिप्शन)
3. Decryption (डिक्रिप्शन)

---

1️⃣ Key Generation:

1. Super-Increasing Sequence W = [w1, w2, w3, ..., wn] चुनें।
2. एक बड़ा integer M चुनें जो ΣW से बड़ा हो।
3. एक integer n चुनें जो M से Co-prime हो (gcd(n, M) = 1)।
4. Public Key बनाएं: B = [b1, b2, ..., bn] जहाँ bi = (wi × n) mod M।
5. Private Key = (W, n, M)

2️⃣ Encryption Process:

Plaintext को Binary Form में बदलें। यदि Binary Message = [x1, x2, ..., xn], तो Ciphertext C निकालें:

C = Σ (xi × bi)

3️⃣ Decryption Process:

1. Private Key का उपयोग करें: Compute n⁻¹ (mod M)।
2. Compute C' = (C × n⁻¹) mod M।
3. अब C' को Super-Increasing Sequence W की मदद से डिकोड करें।

---

उदाहरण:

चरण 1 – Key Generation:

W = [2, 3, 7, 14, 30], M = 61, n = 17 Public Key B = [(2×17)mod61, (3×17)mod61, (7×17)mod61, (14×17)mod61, (30×17)mod61] B = [34, 51, 57, 54, 22]

चरण 2 – Encryption:

Message: 10101 C = (1×34) + (0×51) + (1×57) + (0×54) + (1×22) = 113

चरण 3 – Decryption:

Compute n⁻¹ mod 61 = 18 C' = (113 × 18) mod 61 = 23 अब W = [2, 3, 7, 14, 30] से subset बनाकर 23 प्राप्त करें → {2, 7, 14} → 10101 ✅

---

Knapsack Cryptography की विशेषताएँ:

• Subset Sum Problem पर आधारित।
• Asymmetric Key Cryptosystem।
• Mathematically Complex लेकिन Conceptually Simple।

लाभ:

• सरल संरचना।
• तेज़ एन्क्रिप्शन और डिक्रिप्शन।
• सैद्धांतिक रूप से NP-Complete समस्या पर आधारित सुरक्षा।

सीमाएँ:

• Merkle–Hellman प्रणाली को 1984 में Adi Shamir ने तोड़ दिया।
• Linear Transformations के कारण कमजोर सुरक्षा।
• आज के मानकों के अनुसार असुरक्षित।

वास्तविक उपयोग:

• शैक्षिक अनुसंधान और क्रिप्टोग्राफिक इतिहास में अध्ययन।
• Subset Sum आधारित आधुनिक एल्गोरिद्म में प्रेरणा।
• Post-quantum Cryptography में कुछ वैरिएंट्स का उपयोग।

निष्कर्ष:

Knapsack Cryptography ने Public Key Systems के विकास की दिशा में पहला कदम रखा। यद्यपि यह आज व्यावहारिक रूप से उपयोग नहीं किया जाता, लेकिन इसके सिद्धांतों ने आधुनिक एल्गोरिद्म जैसे RSA, ElGamal और ECC के विकास में महत्वपूर्ण योगदान दिया। यह क्रिप्टोग्राफी के इतिहास में एक मील का पत्थर है।