Lamport signature
کرپٹوگرافی میں، لیمپورٹ سگنیچر یا لیمپورٹ ون ٹائم سگنیچر اسکیم ڈیجیٹل سگنیچر بنانے کا ایک طریقہ ہے۔ لیمپورٹ کے دستخط کسی بھی کرپٹوگرافک طور پر محفوظ یک طرفہ فنکشن سے بنائے جا سکتے ہیں۔ عام طور پر ایک کرپٹوگرافک ہیش فنکشن استعمال کیا جاتا ہے۔ اگرچہ کوانٹم کمپیوٹرز کی ممکنہ ترقی سے کرپٹوگرافی کی بہت سی عام شکلوں جیسے کہ آر ایس اے کی سلامتی کو خطرہ لاحق ہے، لیکن یہ خیال کیا جاتا ہے کہ اس صورت میں بڑے ہیش افعال کے ساتھ لیمپورٹ کے دستخط اب بھی محفوظ ہوں گے۔ ہر لامپورٹ کلید کو صرف ایک پیغام پر دستخط کرنے کے لیے استعمال کیا جا سکتا ہے۔ تاہم، بہت سے لیمپورٹ دستخطوں کو ایک مرکل ہیش ٹری کے ذریعے سنبھالا جا سکتا ہے، اس طرح ایک ہیش ٹری کلید کو بہت سے پیغامات کے لیے استعمال کیا جا سکتا ہے، جس سے یہ کافی موثر ڈیجیٹل دستخطی اسکیم بن جاتی ہے۔ لیمپورٹ دستخطی خفیہ نظام 1979 میں ایجاد کیا گیا تھا اور اس کا نام اس کے موجد لیسلی لیمپورٹ کے نام پر رکھا گیا تھا۔ مثال ایلس میں 256 بٹ کرپٹوگرافک ہیش فنکشن اور کسی قسم کا محفوظ بے ترتیب نمبر جنریٹر ہے۔ وہ لیمپورٹ کلیدی جوڑی بنانا اور استعمال کرنا چاہتی ہے، یعنی ایک نجی کلید اور ایک متعلقہ عوامی کلید۔ کلیدی جوڑا بنانا نجی کلیدی بنانے کے لیے ایلس بے ترتیب نمبر جنریٹر کا استعمال بے ترتیب نمبروں کے 256 جوڑے (مجموعی طور پر 2 × 256 نمبر) تیار کرنے کے لیے کرتی ہے، ہر نمبر کا سائز 256 بٹس ہوتا ہے، یعنی کل 2 × 256 × 256 بٹس = 128 کیبٹ۔ یہ اس کی نجی چابی ہے اور وہ اسے بعد میں استعمال کے لیے کسی محفوظ جگہ پر محفوظ کر لے گی۔ عوامی کلید بنانے کے لیے وہ نجی کلید میں 512 بے ترتیب نمبروں میں سے ہر ایک کو ہیش کرتی ہے، اس طرح 512 ہیش بناتی ہے، ہر ایک کا سائز 256 بٹس ہوتا ہے۔ (اس کے علاوہ مجموعی طور پر 128 کبٹس۔) یہ 512 ہیش اس کی عوامی کلید بناتی ہیں، جسے وہ دنیا کے ساتھ شیئر کرے گی۔ بعد میں پیغام پر دستخط کرتے ہوئے ایلس ایک پیغام پر دستخط کرنا چاہتی ہے۔ پہلے وہ پیغام کو 256 بٹ کی ہیش رقم پر ہیش کرتی ہے۔ پھر، ہیش میں ہر بٹ کے لیے، بٹ کی قیمت کی بنیاد پر، وہ نمبروں کے متعلقہ جوڑوں میں سے ایک نمبر چنتی ہے جو اس کی نجی کلید بناتی ہے (یعنی، اگر بٹ 0 ہے، تو پہلا نمبر منتخب کیا جاتا ہے، اور اگر بٹ 1 ہے، تو دوسرا منتخب کیا جاتا ہے)۔ یہ 256 نمبروں کی ترتیب پیدا کرتا ہے۔ چونکہ ہر نمبر خود 256 بٹس لمبا ہے اس لیے اس کے دستخط کا کل سائز 256 × 256 بٹس = 65536 بٹس = 64 کیبٹ ہوگا۔ یہ (اصل میں تصادفی طور پر منتخب کردہ) نمبر اس کے دستخط ہیں اور وہ انہیں پیغام کے ساتھ شائع کرتی ہے۔ نوٹ کریں کہ اب جب کہ ایلس کی پرائیویٹ کلید استعمال ہو چکی ہے، اسے دوبارہ کبھی استعمال نہیں کیا جانا چاہیے۔ اسے دوسرے 256 نمبروں کو تباہ کرنا ہوگا جو اس نے دستخط کے لیے استعمال نہیں کیے تھے۔ بصورت دیگر، نجی کلید کو دوبارہ استعمال کرنے والے ہر اضافی دستخط مخالفین کے خلاف حفاظتی سطح کو کم کر دیتے ہیں جو بعد میں ان سے جھوٹے دستخط پیدا کر سکتے ہیں۔ دستخط کی تصدیق پھر باب پیغام پر ایلس کے دستخط کی تصدیق کرنا چاہتا ہے۔ وہ 256 بٹ کی ہیش رقم حاصل کرنے کے لیے پیغام کو بھی ہیش کرتا ہے۔ پھر وہ ہیش سم میں بٹس کا استعمال کرتے ہوئے ایلس کی پبلک کلید میں موجود 256 ہیش نکالتا ہے۔ وہ ہیش کو اسی انداز میں چنتا ہے جس طرح ایلس نے دستخط کے لیے بے ترتیب نمبروں کو چن لیا تھا۔ یعنی، اگر میسج ہیش کا پہلا بٹ 0 ہے، تو وہ پہلے جوڑے میں پہلا ہیش چنتا ہے، وغیرہ۔ پھر باب ایلس کے دستخط میں موجود 256 بے ترتیب نمبروں میں سے ہر ایک کو ہیش کرتا ہے۔ اس سے اسے 256 ہیش ملتے ہیں۔ اگر یہ 256 ہیش بالکل ان 256 ہیش سے میل کھاتے ہیں جو اس نے ابھی ایلس کی عوامی کلید سے چنے ہیں تو دستخط ٹھیک ہے۔ اگر نہیں، تو دستخط غلط ہے۔ نوٹ کریں کہ ایلس کے پیغام کے دستخط شائع کرنے سے پہلے، نجی کلید میں 2 × 256 بے ترتیب نمبروں کو کوئی اور نہیں جانتا تھا۔ اس طرح، کوئی اور دستخط کے لیے 256 بے ترتیب نمبروں کی مناسب فہرست نہیں بنا سکتا۔ اور ایلس کے دستخط شائع کرنے کے بعد، دوسرے اب بھی دوسرے 256 بے ترتیب نمبروں کو نہیں جانتے ہیں اور اس طرح وہ ایسے دستخط نہیں بنا سکتے جو دوسرے میسج ہیش کے مطابق ہوں۔ رسمی تفصیل ذیل میں ایک مختصر وضاحت ہے کہ لامپورٹ کے دستخط کیسے کام کرتے ہیں، جو ریاضیاتی اشارے میں لکھے گئے ہیں۔ نوٹ کریں کہ اس تفصیل میں "پیغام" معقول سائز کا ایک مقررہ سائز کا بلاک ہے، ممکنہ طور پر (لیکن ضروری نہیں کہ) صوابدیدی طور پر طویل پیغام پر دستخط کیے جانے کا ہیش نتیجہ ہو۔ چابیاں ایک مثبت عدد ہونے دیں اور پیغامات کا مجموعہ ہونے دیں۔ یک طرفہ فنکشن ہونے دیں۔ کے لیے اور دستخط کنندہ تصادفی طور پر انتخاب کرتا ہے اور حساب کرتا ہے۔ پرائیویٹ کلید، اقدار پر مشتمل ہوتی ہے۔ عوامی کلید اقدار پر مشتمل ہوتی ہے۔ پیغام پر دستخط کرنا ایک پیغام بننے دیں۔ پیغام کا دستخط ہے۔ دستخط کی تصدیق تصدیق کنندہ دستخط کو سب کے لیے چیک کر کے اس کی توثیق کرتا ہے۔ ایک پیغام بنانے کے لیے حو کو یک طرفہ فنکشن کو الٹنا پڑے گا۔ یہ مناسب سائز کے ان پٹ اور آؤٹ پٹ کے لیے ناقابل تلافی سمجھا جاتا ہے۔ حفاظتی پیرامیٹرز لیمپورٹ کے دستخطوں کی سیکیورٹی یک طرفہ ہیش فنکشن کی سیکیورٹی اور اس کی آؤٹ پٹ کی لمبائی پر مبنی ہے۔ ایک ہیش فنکشن کے لیے جو ایک این-بٹ میسج ڈائجسٹ پیدا کرتا ہے، ایک ہیش فنکشن کی دعوت پر مثالی پری امیج اور دوسری پری امیج مزاحمت کا مطلب کلاسیکی کمپیوٹنگ ماڈل کے تحت تصادم تلاش کرنے کے لیے 2n آپریشنز کی ترتیب پر ہوتا ہے۔ گروور کے الگورتھم کے مطابق، کوانٹم کمپیوٹنگ ماڈل کے تحت O (2n/2) آپریشنز پر ایک مثالی ہیش فنکشن کی واحد دعوت پر پری امیج تصادم تلاش کرنا اوپری پابند ہے۔ لیمپورٹ کے دستخطوں میں، عوامی کلید اور دستخط کا ہر بٹ مختصر پیغامات پر مبنی ہوتا ہے جس میں ہیش فنکشن کے لیے صرف ایک دعوت کی ضرورت ہوتی ہے۔ ہر پرائیویٹ کلید وائی، جے اور اس کے متعلقہ زی، جے پبلک کلیدی جوڑے کے لیے، پرائیویٹ کلیدی لمبائی کا انتخاب کرنا ضروری ہے لہذا ان پٹ کی لمبائی پر پری امیج حملہ کرنا آؤٹ پٹ کی لمبائی پر پری امیج حملہ کرنے سے تیز نہیں ہے۔ مثال کے طور پر، ایک انحطاطی صورت میں، اگر ہر نجی کلید yi، j عنصر کی لمبائی صرف 16 بٹس تھی، تو آؤٹ پٹ کے ساتھ مطابقت تلاش کرنے کے لیے 216 کارروائیوں میں تمام 216 ممکنہ نجی کلیدی امتزاج کو مکمل طور پر تلاش کرنا معمولی بات ہے، چاہے پیغام کی ڈائجسٹ لمبائی کچھ بھی ہو۔ لہذا، ایک متوازن نظام ڈیزائن اس بات کو یقینی بناتا ہے کہ دونوں لمبائی تقریبا برابر ہوں۔ گروور کے الگورتھم کی بنیاد پر، ایک کوانٹم سیکیور سسٹم، عوامی کلیدی عناصر زی، جے، نجی کلیدی عناصر وائی، جے اور دستخطی عناصر سی، جے کی لمبائی سسٹم کی سیکیورٹی ریٹنگ سے 2 گنا زیادہ نہیں ہونی چاہیے۔ یعنی: ایک 80 بٹ کا محفوظ نظام 160 بٹ سے کم کی عنصر کی لمبائی کا استعمال کرتا ہے۔ ایک 128 بٹ کا محفوظ نظام 256 بٹ سے کم کی عنصر کی لمبائی کا استعمال کرتا ہے۔ تاہم احتیاط برتنی چاہیے کیونکہ اوپر دیے گئے مثالی کام کے تخمینے ایک مثالی (کامل) ہیش فنکشن کو فرض کرتے ہیں اور ان حملوں تک محدود ہوتے ہیں جو ایک وقت میں صرف ایک ہی پری امیج کو نشانہ بناتے ہیں۔ یہ ایک روایتی کمپیوٹنگ ماڈل کے تحت جانا جاتا ہے کہ اگر 23n/5 پری امیجز کو تلاش کیا جائے تو فی پری امیج کی مکمل لاگت 2n/2 سے کم ہو کر 22n/5 ہو جاتی ہے۔ متعدد پیغامات کے جمع ہونے کو مدنظر رکھتے ہوئے زیادہ سے زیادہ عنصر کے سائز کا انتخاب کرنا ایک کھلا مسئلہ ہے۔ بڑے عنصر کے سائز اور مضبوط ہیش افعال کا انتخاب، جیسے کہ 512 بٹ عناصر اور SHA-512، ان نامعلوم عناصر کو سنبھالنے کے لیے زیادہ حفاظتی مارجن کو یقینی بناتا ہے۔ اصلاح اور متغیرات مختصر نجی کلید نجی کلید کے تمام بے ترتیب نمبروں کو بنانے اور ذخیرہ کرنے کے بجائے، کافی سائز کی ایک واحد کلید کو محفوظ کیا جا سکتا ہے۔ (عام طور پر نجی کلید میں بے ترتیب نمبروں میں سے ایک کے برابر سائز۔) اس کے بعد واحد کلید کو ضرورت پڑنے پر نجی کلید میں تمام بے ترتیب نمبروں کو بنانے کے لیے کرپٹوگرافک طور پر محفوظ سڈورینڈم نمبر جنریٹر (سی ایس پی آر این جی) کے لیے بیج کے طور پر استعمال کیا جا سکتا ہے۔ نوٹ کریں کہ کرپٹوگرافک طور پر محفوظ ہیش (یا کم از کم جس کی آؤٹ پٹ بیج کے ساتھ XOR نہیں ہے) کو CSPRNG کے بجائے استعمال نہیں کیا جا سکتا کیونکہ پیغام پر دستخط کرنے سے نجی کلید سے اضافی بے ترتیب اقدار ظاہر ہوں گی۔ اگر مخالف مطلوبہ وصول کنندگان سے پہلے ہی دستخط تک رسائی حاصل کر سکتا ہے، تو وہ نجی کلید سے ظاہر ہونے والی بے ترتیب اقدار کے ہر دوگنا ہونے کے لیے حفاظتی سطح کو نصف کرنے کے ساتھ جعلی دستخط کر سکتا ہے۔ اسی طرح ایک واحد کلید کو سی ایس پی آر این جی کے ساتھ مل کر بہت سی لیمپورٹ چابیاں بنانے کے لیے استعمال کیا جا سکتا ہے۔ ترجیحی طور پر پھر کسی قسم کی پوسٹ کوانٹم محفوظ بے ترتیب رسائی سی ایس پی آر این جی کا استعمال کیا جانا چاہیے۔ خاص طور پر، کلاسک سی ایس پی آر این جی جیسے بی بی ایس کا استعمال نہیں کیا جانا چاہیے۔ مختصر عوامی کلید اے لیمپورٹ کے دستخط کو ہیش لسٹ کے ساتھ جوڑا جا سکتا ہے، جس سے عوامی کلید میں موجود تمام ہیش کے بجائے صرف ایک ہی ٹاپ ہیش شائع کرنا ممکن ہو جاتا ہے۔ یعنی اقدار کے بجائے۔ سنگل ٹاپ ہیش کے خلاف تصدیق کرنے کے لیے، دستخط میں عوامی کلید کی ہیش لسٹ سے بے ترتیب نمبر اور غیر استعمال شدہ ہیش شامل ہونا چاہیے، جس کے نتیجے میں دستخط تقریبا دوگنا سائز کے ہوں گے۔ یعنی سب کے لیے اقدار کو شامل کرنے کی ضرورت ہے۔ غیر استعمال شدہ ہیش کو دستخط میں شامل کرنے کی ضرورت نہیں ہے اگر ہیش لسٹ کے بجائے کرپٹوگرافک جمع کرنے والا استعمال کیا جاتا ہے۔ مختصر چابیاں اور دستخطی ونٹرنیٹز دستخطی کمپریشن نجی کلید اور عوامی کلید کے سائز کو ایک عنصر سے قدرے کم کر دیتا ہے، اور دستخط کے لیے اس عنصر کا نصف۔ حساب میں ایک عنصر سے قدرے زیادہ اضافہ ہوتا ہے۔ سی ایس پی آر این جی کی ضرورت کے بجائے کرپٹوگرافک طور پر محفوظ ہیش کافی ہے۔ ہیش لسٹ کو دستخط کے سائز کو دوگنا کرنے کی قیمت پر عوامی کلید کو ایک ہی قدر تک مختصر کرنے کے لیے بھی استعمال کیا جا سکتا ہے جیسا کہ پچھلے حصے میں بیان کیا گیا ہے۔ متعدد پیغامات کے لیے عوامی کلید ہر لیمپورٹ عوامی کلید کو صرف ایک پیغام پر دستخط کرنے کے لیے استعمال کیا جا سکتا ہے، جس کا مطلب ہے کہ اگر بہت سے پیغامات پر دستخط کرنے ہیں تو بہت سی چابیاں شائع کرنی پڑتی ہیں۔ لیکن ان عوامی چابیوں پر ہیش ٹری استعمال کیا جا سکتا ہے، اس کے بجائے ہیش ٹری کے ٹاپ ہیش کو شائع کیا جا سکتا ہے۔ اس سے نتیجے میں ہونے والے دستخط کا سائز بڑھ جاتا ہے، کیونکہ ہیش ٹری کی ایک شاخ کو دستخط میں شامل کرنا پڑتا ہے، لیکن اس سے ایک ہیش شائع کرنا ممکن ہو جاتا ہے جسے بعد میں مستقبل کے دستخطوں کی بڑی تعداد کی تصدیق کے لیے استعمال کیا جا سکتا ہے۔ مزید پڑھنے کے لیے S/KEY حوالہ جات دیکھیں۔ L. لامپورٹ، یک طرفہ فنکشن سے ڈیجیٹل دستخطوں کی تعمیر، تکنیکی رپورٹ SRI-CSL-98، SRI انٹرنیشنل کمپیوٹر سائنس لیبارٹری، اکتوبر 1979۔ مرکل کے درختوں کا موثر استعمال-آر ایس اے لیبز مرکل کے درختوں + لیمپورٹ کے دستخطوں کے اصل مقصد کی وضاحت، ایک موثر ون ٹائم سگنیچر اسکیم کے طور پر۔ ہیش پر مبنی دستخطوں اور مرکل کے دستخطوں کا تعارف بذریعہ ایڈم لینگلی۔ BLAKE2b (C + +) کے اوپر لامپورٹ اسکیم کا حوالہ نفاذ حوالہ SHA256، SHA512، یا بلیک 2b (رسٹ) کے اوپر لامپورٹ دستخطوں کا نفاذ ڈیجیٹل دستخطی اسکیمیں ہیش پر مبنی کرپٹوگرافی