پوسٹ کوانٹم کرپٹوگرافی - نیا الگورتھم "60 منٹ میں چلا گیا"

ہم نے PQC کے بارے میں لکھا ہے، اس کے لیے مختصر پوسٹ کوانٹم خفیہ نگاری، کئی بار پہلے۔

اگر آپ نے نام نہاد کوانٹم کمپیوٹنگ کے بارے میں پچھلے کچھ سالوں میں میڈیا کے تمام جوش و خروش کو کھو دیا ہے…

…یہ ہے (اگر آپ اسے معاف کر دیں گے جسے کچھ ماہرین شاید ایک لاپرواہ حد سے زیادہ آسان بنانے پر غور کریں گے) کمپیوٹنگ ڈیوائسز بنانے کا ایک طریقہ ہے جس سے باخبر رہ سکتے ہیں۔ متعدد ممکنہ نتائج ایک ہی وقت میں ایک حساب کی.

بہت احتیاط کے ساتھ، اور شاید تھوڑی قسمت کے ساتھ، اس کا مطلب یہ ہے کہ آپ ہر ممکنہ نتائج کو آزمائے اور جانچے بغیر، درست جواب پر کچھ قسم کے الگورتھم کو گھر پر دوبارہ لکھ سکتے ہیں، یا کم از کم غلط جوابات کو درست طریقے سے رد کر سکتے ہیں۔ ایک ایک کر کے.

کوانٹم کمپیوٹنگ ڈیوائس کا استعمال کرتے ہوئے دو دلچسپ کرپٹ اینالیٹیکل اسپیڈ اپس ممکن ہیں، یہ فرض کرتے ہوئے کہ ایک مناسب طاقتور اور قابل اعتماد کو حقیقت میں بنایا جا سکتا ہے:

• گروور کا کوانٹم سرچ الگورتھم۔ عام طور پر، اگر آپ جوابات کا تصادفی ترتیب شدہ سیٹ تلاش کرنا چاہتے ہیں تاکہ یہ معلوم ہو سکے کہ آیا آپ کا جواب فہرست میں ہے، تو آپ کو قطعی جواب ملنے سے پہلے، بدترین طور پر، پوری فہرست میں ہل چلانے کی توقع ہوگی۔ مثال کے طور پر، اگر آپ کسی دستاویز کو کھولنے کے لیے 128 بٹ AES ڈکرپشن کلید تلاش کرنا چاہتے ہیں، تو آپ کو تمام ممکنہ کلیدوں کی فہرست تلاش کرنے کی ضرورت ہوگی 000..001, ..2, ..3، اور اسی طرح، تمام راستے تک FFF..FFF (16 بائٹس کی مالیت FF)، مسئلہ مکمل ہونے کا یقین کرنے کے لیے۔ دوسرے الفاظ میں، آپ کو تمام 2 کو آزمانے کے لیے بجٹ بنانا ہوگا۔¹²⁸ ممکنہ چابیاں یا تو صحیح کلید تلاش کرنے سے پہلے، یا اس بات کا تعین کرنے سے پہلے کہ کوئی نہیں تھی۔ تاہم، گروور کا الگورتھم، ایک بڑا اور کافی طاقتور کوانٹم کمپیوٹر دیا گیا ہے، یہ دعویٰ کرتا ہے کہ وہ اسی کارنامے کو مکمل کرنے کے قابل ہے۔ مربع جڑ معمول کی کوشش سے، اس طرح کوڈ کو کریک کرنا، تھیوری میں، صرف 2 میں⁶⁴ اس کے بجائے کوشش کرتا ہے.
• شور کا کوانٹم فیکٹرائزیشن الگورتھم۔ کئی عصری انکرپشن الگورتھم اس حقیقت پر انحصار کرتے ہیں کہ دو بڑے پرائم نمبرز کو ایک ساتھ ضرب کرنا تیزی سے کیا جا سکتا ہے، جبکہ ان کے پروڈکٹ کو ان دو نمبروں میں تقسیم کرنا جتنا آپ نے شروع کیا ہے اتنا ہی اچھا ہے۔ اس کا احساس حاصل کرنے کے لیے، قلم اور کاغذ کا استعمال کرتے ہوئے 59×87 کو ضرب کرنے کی کوشش کریں۔ اسے نکالنے میں ایک منٹ لگ سکتا ہے (5133 جواب ہے)، لیکن یہ اتنا مشکل نہیں ہے۔ اب دوسرا طریقہ آزمائیں۔ 4171 کو اس کے دو عوامل میں تقسیم کریں۔ زیادہ مشکل! (یہ 43×97 ہے۔) اب اس کو 600 ہندسوں کی لمبی تعداد کے ساتھ کرنے کا تصور کریں۔ ڈھیلے الفاظ میں، آپ 600 ہندسوں کے نمبر کو ہر ممکنہ 300 ہندسوں کے پرائم نمبر سے تقسیم کرنے کی کوشش میں پھنس گئے ہیں جب تک کہ آپ جیک پاٹ کو نہیں مارتے، یا آپ کو کوئی جواب نہیں ملتا ہے۔ شور کا الگورتھم، تاہم، اس مسئلے کو حل کرنے کا وعدہ کرتا ہے۔ لوگارتھم معمول کی کوشش سے. اس طرح 2048 بائنری ہندسوں کی فیکٹرنگ میں 1024-بٹ نمبر کی فیکٹرنگ کے مقابلے میں صرف دو گنا لمبا ہونا چاہئے، 2047-بٹ نمبر کی فیکٹرنگ سے دوگنا نہیں، ایک بہت بڑی رفتار کی نمائندگی کرتا ہے۔

خطرے کا مقابلہ کرنا

گروور کے الگورتھم کے خطرے کا مقابلہ صرف ان نمبروں کے سائز کو بڑھا کر کیا جا سکتا ہے جو آپ استعمال کر رہے ہیں، جس کا مطلب ہے کہ آپ کے کرپٹوگرافک ہیش یا آپ کی ہم آہنگی انکرپشن کلید میں بٹس کی تعداد کو دوگنا کرنا۔ (دوسرے الفاظ میں، اگر آپ کو لگتا ہے کہ SHA-256 ابھی ٹھیک ہے، تو اس کے بجائے SHA-512 کا استعمال PQC مزاحم متبادل فراہم کرے گا۔)

لیکن شور کے الگورتھم کا مقابلہ اتنی آسانی سے نہیں کیا جا سکتا۔

2048 بٹس کی ایک عوامی کلید کو اس کے سائز میں تیزی سے اضافہ کرنے کی ضرورت ہوگی، نہ کہ صرف مربع کرنے سے، تاکہ 2×2048=4096 بٹس کی کلید کے بجائے، یا تو آپ کو 2 کے ناممکن سائز کے ساتھ ایک نئی کلید کی ضرورت ہوگی۔²⁰⁴⁸ بٹس…

…یا آپ کو پوسٹ کوانٹم انکرپشن سسٹم کی ایک بالکل نئی قسم کو اپنانا ہوگا جس پر شور کا الگورتھم لاگو نہیں ہوتا تھا۔

ٹھیک ہے، امریکی اسٹینڈرڈ باڈی NIST چل رہی ہے۔ PQC "مقابلہ" 2017 کے آخر سے۔

یہ عمل سب کے لیے کھلا ہے، تمام شرکاء کا خیرمقدم ہے، تمام الگورتھم کھلے عام شائع کیے گئے ہیں، اور عوامی جانچ پڑتال محض ممکن نہیں ہے لیکن فعال طور پر حوصلہ افزائی کی:

تجاویز کے لیے کال کریں۔ [بند 2017-11-30]۔ اس کا مقصد یہ ہے کہ نئے عوامی کلیدی خفیہ نگاری کے معیارات ایک یا زیادہ اضافی غیر درجہ بند، عوامی طور پر ظاہر کردہ ڈیجیٹل دستخط، عوامی کلید کی خفیہ کاری، اور کلیدی اسٹیبلشمنٹ الگورتھم کی وضاحت کریں گے جو دنیا بھر میں دستیاب ہیں، اور حکومت کی حساس معلومات کی حفاظت کرنے کے اہل ہیں۔ مستقبل قریب میں، بشمول کوانٹم کمپیوٹرز کی آمد کے بعد۔

گذارشات اور بات چیت کے تین دور کے بعد، NIST نے اعلان کیا۔, 2022-07-05 کو، کہ اس نے چار الگورتھم کا انتخاب کیا ہے جن کو اس نے فوری اثر کے ساتھ "معیارات" سمجھا، سبھی لذت آمیز ناموں کے ساتھ: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON، اور SPHINCS+.

پہلا (CRYSTALS-KYBER) بطور استعمال کیا جاتا ہے جسے a کہا جاتا ہے۔ کلیدی معاہدے کا طریقہ کار (KEM)، جہاں عوامی کمیونیکیشن چینل کے دو سرے محفوظ طریقے سے سیشن کے قابل ڈیٹا کو خفیہ طور پر تبدیل کرنے کے لیے ایک وقتی نجی خفیہ کاری کی کلید بناتے ہیں۔ (سادہ الفاظ میں: جاسوسوں کو صرف کٹی ہوئی گوبھی ملتی ہے، اس لیے وہ بات چیت پر کان نہیں دھر سکتے.)

دیگر تین الگورتھم کے لیے استعمال ہوتے ہیں۔ ڈیجیٹل دستخط، جس کے ذریعے آپ اس بات کو یقینی بنا سکتے ہیں کہ آپ کے آخر میں جو ڈیٹا آپ کو ملا ہے وہ بالکل اسی طرح سے میل کھاتا ہے جو بھیجنے والے نے دوسرے میں ڈالا ہے، اس طرح چھیڑ چھاڑ کو روکنا اور سالمیت کو یقینی بنانا۔ (سادہ الفاظ میں: اگر کوئی ڈیٹا کو کرپٹ یا گڑبڑ کرنے کی کوشش کرتا ہے تو آپ کو پتہ چل جائے گا۔.)

مزید الگورتھم کی ضرورت ہے۔

ایک ہی وقت میں نئے معیارات کا اعلان کرتے ہوئے، NIST نے بھی اعلان کیا۔ چوتھا دور اس کے مقابلے میں، ممکنہ متبادل KEMs کے طور پر مزید چار الگورتھم کو آگے بڑھانا۔ (یاد رکھیں کہ تحریر کے وقت، ہمارے پاس پہلے سے ہی تین منظور شدہ ڈیجیٹل دستخطی الگورتھم ہیں جن میں سے انتخاب کرنا ہے، لیکن صرف ایک سرکاری KEM ہے۔)

یہ تھے: BIKE, Classic McEliece, HQC اور SIKE.

دلچسپ بات یہ ہے کہ میک ایلیس الگورتھم اس کی ایجاد 1970 کی دہائی میں امریکی کرپٹوگرافر رابرٹ میک ایلیس نے کی تھی، جو 2019 میں انتقال کر گئے تھے، جب NIST کا مقابلہ پہلے سے ہی جاری تھا۔

تاہم، یہ کبھی نہیں پکڑا گیا، کیونکہ اس کے لیے اس دن کے مقبول متبادل، Diffie-Hellman-Merkle الگورتھم (DHM، یا کبھی کبھی صرف DH) کے مقابلے میں کلیدی مواد کی بڑی مقدار درکار تھی۔

بدقسمتی سے، تین راؤنڈ فور الگورتھم میں سے ایک، یعنی SIKEایسا لگتا ہے کہ ٹوٹ گیا ہے۔

دماغ کو گھما دینے والے کاغذ میں جس کا عنوان ہے۔ سدھ پر ایک موثر کلیدی بازیابی کا حملہ (ابتدائی ورژن)ایسا لگتا ہے کہ بیلجیئم کے کرپٹوگرافرز Wouter Castryk اور Thomas Decru نے SIKE الگورتھم کو ایک جان لیوا دھچکا لگا ہے

اگر آپ سوچ رہے ہیں تو، SIKE مختصر ہے۔ Supersingular Isogeny Key Encapsulation، اور SIDH کا مطلب ہے۔ سپر سنگولر آئسوجینی ڈفی-ہیل مین، کا ایک مخصوص استعمال SIKE الگورتھم جس کے تحت مواصلاتی چینل کے دو سرے عوامی ڈیٹا کے ایک گروپ کا تبادلہ کرنے کے لیے DHM جیسا "کرپٹوڈانس" انجام دیتے ہیں جو ہر ایک سرے کو ایک وقتی خفیہ خفیہ کاری کی کلید کے طور پر استعمال کرنے کے لیے نجی قدر حاصل کرنے کی اجازت دیتا ہے۔

ہم یہاں حملے کی وضاحت کرنے کی کوشش نہیں کریں گے۔ ہم صرف وہی دہرائیں گے جو کاغذ کا دعویٰ کرتا ہے، یعنی:

بہت ہی ڈھیلے الفاظ میں، یہاں کے ان پٹس میں اس عمل میں استعمال ہونے والے پہلے سے طے شدہ (اور اس وجہ سے عوامی طور پر معروف) پیرامیٹرز کے ساتھ کلیدی اسٹیبلشمنٹ کریپٹوڈنس میں سے ایک کے ذریعہ فراہم کردہ عوامی ڈیٹا شامل ہے۔

لیکن آؤٹ پٹ جو نکالا جاتا ہے (معلومات جس کا حوالہ دیا جاتا ہے۔ isogeny φ اوپر) سمجھا جاتا ہے کہ وہ اس عمل کا کبھی ظاہر نہیں کیا گیا حصہ ہے - نام نہاد نجی کلید۔

دوسرے لفظوں میں، صرف عوامی معلومات سے، جیسے کہ کلیدی سیٹ اپ کے دوران کھلے عام ڈیٹا کا تبادلہ کیا گیا، خفیہ نگاروں کا دعویٰ ہے کہ وہ شرکاء میں سے ایک کی نجی کلید کو بازیافت کرنے کے قابل ہیں۔

اور ایک بار جب آپ میری پرائیویٹ کلید کو جان لیتے ہیں، تو آپ آسانی سے اور ناقابل شناخت طور پر میرے ہونے کا بہانہ کر سکتے ہیں، اس لیے خفیہ کاری کا عمل ٹوٹ جاتا ہے۔

بظاہر، کلیدی کریکنگ الگورتھم کو اپنا کام کرنے میں تقریباً ایک گھنٹہ لگتا ہے، جس طرح کی پروسیسنگ طاقت آپ کو روزمرہ کے لیپ ٹاپ میں ملتی ہے، صرف ایک سی پی یو کور کا استعمال کرتے ہوئے۔

یہ SIKE الگورتھم کے خلاف ہے جب اسے لیول 1، NIST کے بنیادی درجے کے خفیہ کاری سیکیورٹی کو پورا کرنے کے لیے ترتیب دیا گیا ہے۔

کیا کیا جائے؟

کچھ بھی نہیں!

(یہ اچھی خبر ہے۔)

جیسا کہ مقالے کے مصنفین کا مشورہ ہے، یہ نوٹ کرنے کے بعد کہ ان کا نتیجہ ابھی ابتدائی ہے، "موجودہ صورتحال کے ساتھ، ایسا لگتا ہے کہ SIDH کسی بھی عوامی طور پر تیار کردہ بنیادی وکر کے لیے مکمل طور پر ٹوٹا ہوا ہے۔"

(یہ بری خبر ہے۔)

تاہم، یہ بتا دیں کہ SIKE الگورتھم ابھی تک سرکاری طور پر منظور نہیں ہوا ہے، اب اسے یا تو اس مخصوص حملے کو ناکام بنانے کے لیے ڈھال لیا جا سکتا ہے (ایسی چیز جس کا مصنفین اعتراف کر سکتے ہیں)، یا اسے مکمل طور پر چھوڑ دیا گیا ہے۔

آخر کار SIKE کے ساتھ جو بھی ہوتا ہے، یہ اس بات کی ایک بہترین یاد دہانی ہے کہ آپ کے اپنے انکرپشن الگورتھم کو ایجاد کرنے کی کوشش کیوں خطرے سے بھری ہوئی ہے۔

یہ بھی ایک واضح مثال ہے کہ ملکیتی خفیہ کاری کے نظام کیوں جو خود الگورتھم کی رازداری پر انحصار کرتا ہے۔ ان کی حفاظت کو برقرار رکھنا 2022 میں ناقابل قبول ہے۔

اگر PQC الگورتھم جیسا کہ SIKE دنیا بھر کے ماہرین کی طرف سے پانچ سال سے زیادہ عرصے تک مسلسل اور تحقیقات میں زندہ رہا، اس کے باوجود کہ اسے خاص طور پر ظاہر کیا جائے تاکہ اسے عوامی جانچ پڑتال کا نشانہ بنایا جا سکے…

…پھر اپنے آپ سے یہ پوچھنے کی کوئی ضرورت نہیں ہے کہ جب آپ کے گھر میں بنائے گئے، چھپے ہوئے انکرپشن الگورتھم کو جنگل میں چھوڑے جانے کا امکان ہے!

---