তথ্য সুরক্ষায় বিচ্ছিন্ন লগারিদমিক সমস্যা কী?

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

তদুপরি, g সংজ্ঞায়িত এই জাতীয় যেকোন দুটি পূর্ণসংখ্যা হবে সর্বসম্মত মডুলো n। এটি একটি ফাংশন লগ_b উপস্থাপন করতে পারে :G → Z_n (যেখানে Z_n পূর্ণসংখ্যার রিং নির্দেশ করে মডুলো n) কে তৈরি করে k মডুলো n-এর সঙ্গতি শ্রেণী। এই ফাংশনটি হল একটি গ্রুপ আইসোমরফিজম যা বিযুক্ত অ্যালগরিদম থেকে বেস বি.

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

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

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

পাবলিক-কী ক্রিপ্টোসিস্টেম বাস্তবায়নের জন্য প্রয়োজনীয় সর্বাগ্রে টুল হল ডিসক্রিট লগ সমস্যা (DLP)। কিছু জনপ্রিয় আধুনিক ক্রিপ্টো-অ্যালগরিদম রয়েছে যা তাদের নিরাপত্তার ভিত্তি করে DLP-তে। এটি এই সমস্যার জটিলতার উপর ভিত্তি করে। ডিফি-হেলম্যান 1976 সালে সুপরিচিত ডিফি-হেলম্যান কী চুক্তি প্রকল্পের পরামর্শ দেন।

উদাহরণ

• বিচ্ছিন্ন লগারিদমগুলি গ্রুপে শেখা সবচেয়ে সহজ (Z_p ) এটি হল গুনগত মডিউলের অধীনে একম শ্রেণির (1,…., p – 1) গ্রুপ, প্রাইম p৷

• যদি এই গোষ্ঠীর একটি সংখ্যার kth শক্তি খুঁজে বের করার প্রয়োজন হয়, তাহলে এটি একটি পূর্ণসংখ্যা হিসাবে এর kth শক্তি আবিষ্কার করে এবং তারপর p দ্বারা ভাগ করার পরে অবশিষ্টাংশ আবিষ্কার করে তা করতে পারে৷

• এই প্রক্রিয়াটি বিযুক্ত ব্যাখ্যা হিসাবে পরিচিত।

• উদাহরণস্বরূপ, বিবেচনা করুন (Z₁₇ ) ^x . এটি 3 ⁴ গণনা করতে পারে এই গ্রুপে, এটি প্রথমে 3 ⁴ গণনা করতে পারে =81, এবং এইভাবে এটি 81 কে 17 দ্বারা ভাগ করে বাকি 13 অর্জন করতে পারে।

• তাই, 3 ⁴ গ্রুপে =13 (Z₁₇ ) ^x . বিযুক্ত লগারিদম শুধুমাত্র বিপরীত অপারেশন। উদাহরণস্বরূপ, এটি 3 ^k সমীকরণটি নিতে পারে k.

  এর জন্য =13 (mod 17)

• এই k =4 একটি সমাধান. 3 ¹⁶ থেকে ≡ 1(mod 17), এটি আরও অনুসরণ করে যে n যদি পূর্ণসংখ্যা হয় তাহলে 3 ⁴⁺¹⁶ⁿ ≡ 13 x 1 ⁿ ≡ 13 (মোড 17)।

• অতএব, সমীকরণটিতে 4 + 16n ফর্মের অসীম কিছু সমাধান রয়েছে। উপরন্তু, কারণ 16 হল ক্ষুদ্রতম ধনাত্মক পূর্ণসংখ্যা m সন্তোষজনক3 ^m ≡ 1 (mod 17), i. e , 16 হল 3 ইঞ্চির ক্রম (Z₁₇ ) ^x , একমাত্র সমাধান আছে. একইভাবে, সমাধানটিকে k ≡ 4 (mod)16 হিসাবে সংজ্ঞায়িত করা যেতে পারে।

• সাধারণ বিযুক্ত লগারিদমসলগ_b গণনা করার জন্য কোন দক্ষ অ্যালগরিদম নেই g পরিচিত।