পোস্ট-কোয়ান্টাম ক্রিপ্টোগ্রাফি - নতুন অ্যালগরিদম "60 মিনিটের মধ্যে চলে গেছে"

আমরা PQC সম্পর্কে লিখেছি, সংক্ষেপে পোস্ট-কোয়ান্টাম ক্রিপ্টোগ্রাফি, আগে বেশ কয়েকবার।

যদি আপনি তথাকথিত কোয়ান্টাম কম্পিউটিং সম্পর্কে গত কয়েক বছরের সমস্ত মিডিয়া উত্তেজনা মিস করেছেন…

…এটি হল (যদি আপনি ক্ষমা করবেন যা কিছু বিশেষজ্ঞ সম্ভবত একটি বেপরোয়া অতিরিক্ত সরলীকরণ বিবেচনা করবেন) কম্পিউটিং ডিভাইস তৈরির একটি উপায় যা ট্র্যাক রাখতে পারে একাধিক সম্ভাব্য ফলাফল একই সময়ে একটি গণনার।

অনেক যত্নের সাথে, এবং সম্ভবত কিছুটা ভাগ্যের সাথে, এর মানে হল যে আপনি কিছু ধরণের অ্যালগরিদম সঠিক উত্তরে বাড়িতে লিখতে পারেন, বা অন্ততপক্ষে সঠিকভাবে ভুল উত্তরগুলির একটি সম্পূর্ণ বর্জন করতে পারেন, প্রতিটি সম্ভাব্য ফলাফলের চেষ্টা এবং পরীক্ষা না করেই। একটার পর একটা.

একটি কোয়ান্টাম কম্পিউটিং ডিভাইস ব্যবহার করে দুটি আকর্ষণীয় ক্রিপ্টানালিটিকাল স্পিডআপ সম্ভব, অনুমান করে একটি উপযুক্ত শক্তিশালী এবং নির্ভরযোগ্য একটি আসলে তৈরি করা যেতে পারে:

• গ্রোভারের কোয়ান্টাম অনুসন্ধান অ্যালগরিদম। সাধারণত, যদি আপনি তালিকায় আপনারটি আছে কিনা তা দেখতে এলোমেলোভাবে ক্রমানুসারে উত্তরের সেট অনুসন্ধান করতে চান, তাহলে আপনি একটি নির্দিষ্ট উত্তর পাওয়ার আগে, সবচেয়ে খারাপভাবে পুরো তালিকার মধ্য দিয়ে লাঙ্গল করার আশা করবেন। উদাহরণস্বরূপ, যদি আপনি একটি নথিকে আনস্ক্র্যাম্বল করার জন্য 128-বিট AES ডিক্রিপশন কী খুঁজে পেতে চান, তাহলে আপনাকে সব সম্ভাব্য কীগুলির তালিকা অনুসন্ধান করতে হবে, থেকে শুরু করে 000..001, ..2, ..3, এবং তাই, সব উপায় পর্যন্ত FFF..FFF (16 বাইট' মূল্য FF), সমস্যাটি সম্পূর্ণ করার বিষয়ে নিশ্চিত হতে। অন্য কথায়, সমস্ত 2 চেষ্টা করার জন্য আপনাকে বাজেট করতে হবে¹²⁸ সম্ভাব্য কীগুলি হয় সঠিক কী খুঁজে পাওয়ার আগে, অথবা একটি ছিল না তা নির্ধারণ করার আগে। গ্রোভারের অ্যালগরিদম, তবে, একটি বড় এবং যথেষ্ট শক্তিশালী কোয়ান্টাম কম্পিউটার দেওয়া হয়েছে, দাবি করে যে তারা একই কৃতিত্ব সম্পন্ন করতে সক্ষম হবে। বর্গমূল স্বাভাবিক প্রচেষ্টার, এইভাবে কোড ক্র্যাকিং, তত্ত্বে, মাত্র 2⁶⁴ পরিবর্তে চেষ্টা করে।
• শোর কোয়ান্টাম ফ্যাক্টরাইজেশন অ্যালগরিদম। বেশ কিছু সমসাময়িক এনক্রিপশন অ্যালগরিদম এই সত্যটির উপর নির্ভর করে যে দুটি বড় মৌলিক সংখ্যাকে একসাথে গুণ করা দ্রুত করা যেতে পারে, যেখানে আপনি যে দুটি সংখ্যা দিয়ে শুরু করেছেন তার মধ্যে তাদের গুণফলকে ভাগ করা যতটা অসম্ভব। এটির জন্য একটি অনুভূতি পেতে, কলম এবং কাগজ ব্যবহার করে 59×87 গুণ করার চেষ্টা করুন। এটি বের করতে এক মিনিট বা তার বেশি সময় লাগতে পারে (5133 হল উত্তর), কিন্তু এটি এতটা কঠিন নয়। এখন অন্যভাবে চেষ্টা করুন। ভাগ করুন, বলুন, 4171 এর দুটি কারণের মধ্যে ফিরে আসুন। অনেক কঠিন! (এটি 43×97।) এখন 600 ডিজিট লম্বা একটি সংখ্যা দিয়ে এটি করার কল্পনা করুন। ঢিলেঢালাভাবে বলতে গেলে, আপনি 600 ডিজিটের সংখ্যাটিকে প্রতিটি সম্ভাব্য 300 ডিজিটের মৌলিক সংখ্যা দ্বারা ভাগ করার চেষ্টা করে আটকে থাকবেন যতক্ষণ না আপনি জ্যাকপটে আঘাত করছেন, বা কোনও উত্তর খুঁজে পাচ্ছেন না। Shor এর অ্যালগরিদম, যাইহোক, সঙ্গে এই সমস্যা সমাধানের প্রতিশ্রুতি লগারিদম স্বাভাবিক প্রচেষ্টার। এইভাবে 2048 বাইনারি ডিজিটগুলির একটি সংখ্যার ফ্যাক্টরিং একটি 1024-বিট সংখ্যার ফ্যাক্টরিংয়ের চেয়ে দ্বিগুণ সময় নিতে হবে, একটি 2047-বিট নম্বরের ফ্যাক্টরিংয়ের চেয়ে দ্বিগুণ নয়, একটি বিশাল গতির প্রতিনিধিত্ব করে।

হুমকি মোকাবেলা

গ্রোভারের অ্যালগরিদম থেকে হুমকির মোকাবিলা করা যেতে পারে আপনি যে সংখ্যাগুলি ব্যবহার করছেন সেগুলিকে স্কোয়ার করে আকার বাড়িয়ে দিয়ে, যার অর্থ আপনার ক্রিপ্টোগ্রাফিক হ্যাশ বা আপনার সিমেট্রিক এনক্রিপশন কীতে বিটের সংখ্যা দ্বিগুণ করা। (অন্য কথায়, আপনি যদি মনে করেন SHA-256 এখনই ঠিক আছে, তাহলে এর পরিবর্তে SHA-512 ব্যবহার করলে একটি PQC-প্রতিরোধী বিকল্প পাওয়া যাবে।)

কিন্তু শোর অ্যালগরিদম এত সহজে মোকাবেলা করা যায় না।

2048 বিটের একটি পাবলিক কী এর আকার দ্রুতগতিতে বাড়ানোর প্রয়োজন হবে, শুধুমাত্র স্কোয়ার করে নয়, যাতে 2×2048=4096 বিটের একটি কীর পরিবর্তে, হয় আপনার 2 এর অসম্ভব আকারের একটি নতুন কী প্রয়োজন।²⁰⁴⁸ বিট

…অথবা আপনাকে একটি সম্পূর্ণ নতুন ধরণের পোস্ট-কোয়ান্টাম এনক্রিপশন সিস্টেম গ্রহণ করতে হবে যেখানে শোর অ্যালগরিদম প্রযোজ্য নয়।

ঠিক আছে, ইউএস স্ট্যান্ডার্ড বডি এনআইএসটি একটি চলছে PQC "প্রতিযোগিতা" 2017 এর শেষের দিক থেকে।

প্রক্রিয়াটি সকলের জন্য উন্মুক্ত করা হয়েছে, সমস্ত অংশগ্রহণকারীদের স্বাগত সহ, সমস্ত অ্যালগরিদম প্রকাশ্যে প্রকাশ করা হয়েছে এবং জনসাধারণের যাচাই-বাছাই কেবল সম্ভব নয় কিন্তু সক্রিয়ভাবে উত্সাহিত করা হয়:

প্রস্তাব জন্য কল. [বন্ধ 2017-11-30]। [...] এটা উদ্দেশ্য যে নতুন পাবলিক-কী ক্রিপ্টোগ্রাফি মান এক বা একাধিক অতিরিক্ত অশ্রেণীবদ্ধ, সর্বজনীনভাবে প্রকাশ করা ডিজিটাল স্বাক্ষর, পাবলিক-কী এনক্রিপশন, এবং কী-প্রতিষ্ঠা অ্যালগরিদম নির্দিষ্ট করবে যা বিশ্বব্যাপী উপলব্ধ, এবং সংবেদনশীল সরকারি তথ্য রক্ষা করতে সক্ষম। কোয়ান্টাম কম্পিউটারের আবির্ভাবের পরে সহ অদূর ভবিষ্যতে।

তিন দফা দাখিল ও আলোচনার পর, NIST ঘোষণা করেছে, 2022-07-05-এ, যে এটি চারটি অ্যালগরিদম বেছে নিয়েছে যেটিকে এটি অবিলম্বে "মান" হিসাবে বিবেচনা করেছে, সবগুলোই আনন্দদায়ক শব্দের নাম রয়েছে: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, এবং SPHINCS+.

প্রথমটি (CRYSTALS-KYBER) একটি বলা হয় হিসাবে ব্যবহৃত হয় মূল চুক্তি প্রক্রিয়া (কেইএম), যেখানে একটি পাবলিক কমিউনিকেশন চ্যানেলের দুটি প্রান্ত নিরাপদে গোপনীয়ভাবে একটি সেশনের মূল্যের ডেটা বিনিময়ের জন্য একটি এককালীন ব্যক্তিগত এনক্রিপশন কী তৈরি করে। (সহজভাবে করা: স্নুপাররা কেবল কাটা বাঁধাকপি পায়, তাই তারা কথোপকথন শুনতে পারে না.)

অন্য তিনটি অ্যালগরিদম এর জন্য ব্যবহৃত হয় ডিজিটাল স্বাক্ষর, যার মাধ্যমে আপনি নিশ্চিত করতে পারেন যে আপনার শেষে যে ডেটা আপনি পেয়েছেন তা প্রেরক অন্যের কাছে যা রেখেছেন তার সাথে ঠিক মেলে, এইভাবে টেম্পারিং প্রতিরোধ করে এবং অখণ্ডতা নিশ্চিত করে৷ (সহজভাবে করা: যদি কেউ দুর্নীতি বা ডেটা নিয়ে বিশৃঙ্খলা করার চেষ্টা করে, আপনি জানতে পারবেন.)

আরো অ্যালগরিদম প্রয়োজন

একই সময়ে নতুন মান ঘোষণা করার সময়, NIST একটি ঘোষণা করেছে চতুর্থ রাউন্ড এর প্রতিযোগিতায়, সম্ভাব্য বিকল্প কেইএম হিসাবে আরও চারটি অ্যালগরিদম এগিয়ে রাখছে। (মনে রাখবেন, লেখার সময়, আমাদের কাছে ইতিমধ্যেই বেছে নেওয়ার জন্য তিনটি অনুমোদিত ডিজিটাল স্বাক্ষর অ্যালগরিদম আছে, কিন্তু শুধুমাত্র একটি অফিসিয়াল কেইএম।)

এই ছিল: BIKE, Classic McEliece, HQC এবং SIKE.

চমকপ্রদভাবে, দ McEliece অ্যালগরিদম 1970 এর দশকে আমেরিকান ক্রিপ্টোগ্রাফার রবার্ট ম্যাক এলিস দ্বারা উদ্ভাবিত হয়েছিল, যিনি 2019 সালে মারা গিয়েছিলেন, NIST-এর প্রতিযোগিতা ইতিমধ্যেই চলার পরে।

যদিও এটি কখনই ধরা পড়েনি, কারণ দিনের জনপ্রিয় বিকল্প ডিফি-হেলম্যান-মার্কেল অ্যালগরিদম (ডিএইচএম, বা কখনও কখনও কেবল ডিএইচ) এর তুলনায় এটির জন্য প্রচুর পরিমাণে মূল উপাদানের প্রয়োজন ছিল।

দুর্ভাগ্যবশত, তিনটি রাউন্ড ফোর অ্যালগরিদমের মধ্যে একটি, যথা SIKE, ফাটল হয়েছে বলে মনে হচ্ছে।

শিরোনাম একটি মস্তিষ্ক-মোচন কাগজে একটি কার্যকরী মূল পুনরুদ্ধার আক্রমণ সিধে (প্রাথমিক সংস্করণ), বেলজিয়ান ক্রিপ্টোগ্রাফার Wouter Castryk এবং Thomas Decru মনে হচ্ছে SIKE অ্যালগরিদমকে মারাত্মক আঘাত করেছে

আপনি যদি ভাবছেন, SIKE এর জন্য ছোট সুপারসিঙ্গুলার আইসোজেনি কী এনক্যাপসুলেশন, এবং SIDH মানে সুপারসিঙ্গুলার আইসোজেনি ডিফি-হেলম্যান, একটি নির্দিষ্ট ব্যবহার SIKE অ্যালগরিদম যেখানে একটি যোগাযোগ চ্যানেলের দুটি প্রান্ত একটি DHM-এর মতো "ক্রিপ্টোড্যান্স" সম্পাদন করে একগুচ্ছ পাবলিক ডেটা বিনিময় করতে যা প্রতিটি প্রান্তকে একটি এককালীন গোপন এনক্রিপশন কী হিসাবে ব্যবহার করার জন্য একটি ব্যক্তিগত মান অর্জন করতে দেয়।

আমরা এখানে আক্রমণ ব্যাখ্যা করার চেষ্টা করতে যাচ্ছি না; কাগজটি যা দাবি করে আমরা তা পুনরাবৃত্তি করব, যথা:

খুব ঢিলেঢালাভাবে বললে, এখানে ইনপুটগুলি প্রক্রিয়ায় ব্যবহৃত পূর্ব-নির্ধারিত (এবং তাই সর্বজনীনভাবে পরিচিত) প্যারামিটারগুলির সাথে মূল প্রতিষ্ঠা ক্রিপ্টোড্যান্সের একজন অংশগ্রহণকারীর দ্বারা সরবরাহ করা সর্বজনীন ডেটা অন্তর্ভুক্ত করে।

কিন্তু যে আউটপুটটি বের করা হয়েছে (তথ্য হিসাবে উল্লেখ করা হয়েছে আইসোজেনি φ উপরের) প্রক্রিয়াটির কখনোই প্রকাশ না করা অংশ বলে মনে করা হয় - তথাকথিত ব্যক্তিগত কী।

অন্য কথায়, শুধুমাত্র জনসাধারণের তথ্য থেকে, যেমন কী সেটআপের সময় খোলাখুলিভাবে আদান-প্রদান করা ডেটা, ক্রিপ্টোগ্রাফাররা দাবি করে যে তারা অংশগ্রহণকারীদের একজনের ব্যক্তিগত কী পুনরুদ্ধার করতে সক্ষম হয়েছে।

এবং একবার আপনি আমার ব্যক্তিগত কী জানলে, আপনি সহজেই এবং অজ্ঞাতভাবে আমি হওয়ার ভান করতে পারেন, তাই এনক্রিপশন প্রক্রিয়াটি ভেঙে গেছে।

স্পষ্টতই, কী-ক্র্যাকিং অ্যালগরিদমটি কাজ করতে প্রায় এক ঘন্টা সময় নেয়, শুধুমাত্র একটি সিপিইউ কোর ব্যবহার করে যে ধরনের প্রসেসিং শক্তি আপনি প্রতিদিনের ল্যাপটপে পাবেন।

এটি SIKE অ্যালগরিদমের বিরুদ্ধে যখন লেভেল 1, NIST-এর এনক্রিপশন নিরাপত্তার মৌলিক গ্রেড পূরণ করতে কনফিগার করা হয়।

কি করো?

কিছুই নেই!

(এটাই ভালো খবর।)

কাগজের লেখকরা পরামর্শ দেন যে, তাদের ফলাফল এখনও প্রাথমিক অবস্থায় রয়েছে, "বর্তমান অবস্থার সাথে, SIDH যেকোন সর্বজনীনভাবে উত্পন্ন বেস কার্ভের জন্য সম্পূর্ণভাবে ভেঙে গেছে বলে মনে হচ্ছে।"

(এটা খারাপ খবর।)

যাইহোক, বলুন যে SIKE অ্যালগরিদম এখনও আনুষ্ঠানিকভাবে অনুমোদিত নয়, এটি এখন হয় এই বিশেষ আক্রমণকে ব্যর্থ করার জন্য অভিযোজিত করা যেতে পারে (লেখকরা স্বীকার করেছেন যে এটি সম্ভব হতে পারে), বা একেবারে বাদ দেওয়া যেতে পারে।

SIKE-তে শেষ পর্যন্ত যাই ঘটুক না কেন, আপনার নিজের এনক্রিপশন অ্যালগরিদম উদ্ভাবন করার চেষ্টা করা কেন বিপদে পরিপূর্ণ তার এটি একটি চমৎকার অনুস্মারক।

এটি কেন মালিকানা এনক্রিপশন সিস্টেমের একটি সূক্ষ্ম উদাহরণ যে অ্যালগরিদমের গোপনীয়তার উপর নির্ভর করে তাদের নিরাপত্তা বজায় রাখা 2022 সালে কেবল অগ্রহণযোগ্য।

যদি SIKE-এর মতো একটি PQC অ্যালগরিদম পাঁচ বছরেরও বেশি সময় ধরে বিশ্বব্যাপী বিশেষজ্ঞদের দ্বারা নিয়ন্ত্রিত এবং অনুসন্ধানে টিকে থাকে, বিশেষভাবে প্রকাশ করা সত্ত্বেও যাতে এটি জনসাধারণের যাচাই-বাছাইয়ের শিকার হতে পারে...

…তাহলে নিজেকে জিজ্ঞাসা করার দরকার নেই যে আপনার বাড়িতে তৈরি, লুকানো-থেকে-ভিউ এনক্রিপশন অ্যালগরিদমগুলি বন্যের মধ্যে ছেড়ে দেওয়ার সময় কতটা ভাল হতে পারে!

---