তথ্য নিরাপত্তায় ডিসক্রিট লগারিদমিক সমস্যা কী?

মনে করুন G হল একটি সসীম চক্রিক সেট যার n উপাদান রয়েছে। ধরে নিই গ্রুপটি গুণনীয়ভাবে লেখা হয়েছে। b হল G-এর একটি জেনারেটর এবং তাই G-এর প্রতিটি উপাদান g কে g = b^k আকারে লেখা যেতে পারে কিছু পূর্ণসংখ্যা k-এর জন্য।

অতএব, g কে সংজ্ঞায়িত এমন যেকোনো দুটি পূর্ণসংখ্যা n মডুলো কনগ্রুয়েন্ট হবে। আমরা একটি ফাংশন log_b: G → Z_n সংজ্ঞায়িত করতে পারি (যেখানে Z_n n মডুলো পূর্ণসংখ্যার রিং বোঝায়) g কে k-এর কনগ্রুয়েন্স ক্লাস নির্ধারণ করে mডুলো n। এই ফাংশনটি একটি গ্রুপ আইসোমরফিজম যাকে বেস b-এ ডিসক্রিট লগারিদম বলা হয়।

গণিতে, বিশেষত trừপারার বীজগণিতে এবং এর প্রয়োগে, ডিসক্রিট লগারিদম সাধারণ লগারিদমের সেট থিয়োরেটিক অনুবাদ। বিশেষভাবে, একটি সাধারণ লগারিদম log_a(b) হলো সমীকরণ a^x = b এর একটি সমাধান বাস্তব বা জটিল সংখ্যার ওপর।

একইভাবে, যদি g এবং h একটি সসীম চক্রিক গ্রুপ G-এর উপাদান হয়, তবে সমীকরণ g^x = h এর একটি সমাধান x কে h-এর বেস g-এ ডিসক্রিট লগারিদম বলা হয় গ্রুপ G-তে।

ডিসক্রিট লগের সংখ্যা তত্ত্বে এক বড় ইতিহাস রয়েছে। মূলত, সেগুলি সসীম ক্ষেত্রে গণনায় ব্যবহৃত হতো। যাইহোক, সেগুলি কেবল পূর্ণসংখ্যা উৎপাদন সমস্যা (IFP) এর মতো অস্পষ্ট ছিল।

পাবলিক-কী ক্রিপ্টোসিস্টেম বাস্তবায়নের জন্য পরম দরকারি টুল হলো ডিসক্রিট লগ প্রობ্লেম (DLP)। কিছু জনপ্রিয় আধুনিক ক্রিপ্টো-অ্যালগরিদম তাদের নিরাপত্তা DLP-র ওপর ভিত্তি করে। এটি এই সমস্যার জটিলতার ওপর ভিত্তি করে। ডিফি-হেলম্যান ১৯৭৬ সালে বিখ্যাত ডিফি-হেলম্যান কী চুক্তি স্কিম প্রস্তাব করেছিলেন।

উদাহরণ

• ডিসক্রিট লগারিদম গ্রুপ (Z_p) তে শিখা সবচেয়ে সহজ। এটি কনগ্রুয়েন্স ক্লাসের গ্রুপ (১, ..., p-1) গুণন মডুলো, প্রাইম p।
• যদি এই গ্রুপের szám-এ একটার k-তম শক্তি খুঁজে বের করতে হয়, তবে এটি করে তার k-তম শক্তি পূর্ণসংখ্যা হিসেবে খুঁজে বের করে এবং তারপর p দ্বারা ভাগ করার পর অবশিষ্টাংশ খুঁজে বের করে।
• এই প্রক্রিয়াকে ডিসক্রিট এক্সপোনেনশিয়েশন বলা হয়।
• উদাহরণস্বরূপ, (Z₁₇)^x বিবেচনা করুন। আমরা 3⁴ এই গ্রুপে গণনা করতে চাই, প্রথমে 3⁴ = ৮১ হিসাব করি, এবং তারপর ৮১ কে ১৭ দিয়ে ভাগ করি ১৩ অবশিষ্টাংশ পাওয়ার জন্য।
• অতএব, 3⁴ = ১৩ গ্রুপ (Z₁₇)^x এ। ডিসক্রিট লগারিদম শুধু বিপরীত অপারেশন। উদাহরণস্বরূপ, সমীকরণ 3^k = ১৩ (mod 17) কে k-এর জন্য নিন।
• এখানে k = ৪ একটি সমাধান। যেহেতু 3¹⁶ ≡ ১ (mod 17), তাই এটি অনুসরণ করে যে যদি n একটি পূর্ণসংখ্যা হয় তবে 3⁴⁺¹⁶ⁿ ≡ ১৩ × ১ⁿ ≡ ১৩ (mod 17)।
• অতএব, সমীকরণটির অসংখ্য সমাধান রয়েছে ৪ + ১৬n আকারে। আরও, যেহেতু ১৬ হলো সবচেয়ে ছোট ধনাত্মক পূর্ণসংখ্যা m যা 3^m ≡ ১ (mod 17) সন্তুষ্ট করে, অর্থাৎ, ১৬ হলো (Z₁₇)^x এ ৩-এর অর্ডার, তাই কেবল এই সমাধানগুলি রয়েছে। একইভাবে, সমাধানকে সংজ্ঞায়িত করা যেতে পারে k ≡ ৪ (mod 16)।
• সাধারণ ডিসক্রিট লগারিদম log_bg গণনা করার জন্য কোনো দক্ষ অ্যালগরিদম জানা নেই।