MMH-Badger MAC
بیجر ایک پیغام کی تصدیق کا کوڈ (ایم اے سی) ہے جو عالمگیر ہیشنگ کے خیال پر مبنی ہے اور اسے بوسگارڈ، سکاوینیئس، پیڈرسن، کرسٹینسن اور زینر نے تیار کیا تھا۔ یہ ای این ایچ (نیچے دیکھیں) کے اطلاق کے بعد ایک ε-سب سے زیادہ مضبوطی سے عالمگیر (اے ایس یو) ہیش فنکشن فیملی کا استعمال کرتے ہوئے، جہاں ε کی قدر ہے، کو مضبوط بنا کر بنایا گیا ہے۔ چونکہ بیجر ایک MAC فنکشن ہے جو یونیورسل ہیش فنکشن اپروچ پر مبنی ہے، اس لیے بیجر کی سیکیورٹی کے لیے درکار شرائط وہی ہیں جو دیگر یونیورسل ہیش فنکشنز جیسے UMAC کے لیے ہیں۔ تعارف بیجر میک بٹس تک لمبائی کے پیغام پر کارروائی کرتا ہے اور لمبائی بٹس کا تصدیق ٹیگ واپس کرتا ہے، جہاں۔ حفاظتی ضروریات کے مطابق، صارف بیجر میں متوازی ہیش درختوں کی تعداد کا انتخاب کر سکتا ہے۔ کوئی بھی یو کی بڑی اقدار کا انتخاب کر سکتا ہے، لیکن وہ اقدار ایم اے سی کی سلامتی کو مزید متاثر نہیں کرتی ہیں۔ الگورتھم ایک 128 بٹ کلید کا استعمال کرتا ہے اور اس کلید کے تحت کارروائی کرنے کے لیے محدود پیغام کی لمبائی ہے۔ کسی دی گئی کلید کے تحت بیجر الگورتھم کو چلانے کے لیے کلیدی سیٹ اپ کو فی کلید صرف ایک بار چلانا پڑتا ہے، کیونکہ ایم اے سی کی نتیجے میں اندرونی حالت کو کسی دوسرے پیغام کے ساتھ استعمال کرنے کے لیے محفوظ کیا جا سکتا ہے جس پر بعد میں کارروائی کی جائے گی۔ نئے ہیش خاندانوں کو حاصل کرنے کے لیے ای این ایچ ہیش خاندانوں کو جوڑا جا سکتا ہے۔ ε-AU، ε-AV، اور ε-ASU خاندانوں کے لیے، مؤخر الذکر سابقہ میں موجود ہیں۔ مثال کے طور پر، ایک اے۔ یو۔ یو خاندان بھی ایک اے۔ یو خاندان ہے، ایک اے۔ ایس۔ یو بھی ایک اے۔ یو۔ یو خاندان ہے، وغیرہ۔ دوسری طرف، ایک مضبوط خاندان کو کمزور خاندان میں تبدیل کیا جا سکتا ہے، جب تک کہ کارکردگی میں اضافہ حاصل کیا جا سکے۔ یونیورسل ہیش فنکشن کو یونیورسل ہیش فنکشن میں کم کرنے کا ایک طریقہ درج ذیل میں بیان کیا جائے گا۔ نظریہ 2 ایک سیٹ A سے لے کر سیٹ B تک ایک ε-AδU ہیش خاندان ہونے دیں۔ ایک پیغام پر غور کریں۔ پھر افعال پر مشتمل خاندان H ε-AU ہے۔ اگر، تو وہ امکان جو زیادہ سے زیادہ ε ہے، چونکہ ایک ε-A अनेदि خاندان ہے۔ اگر لیکن، تو امکان معمولی طور پر 0 ہے۔ نظریہ 2 کا ثبوت ENH-خاندان میں بیان کیا گیا تھا جو عالمگیر ہیش خاندان NH (جو UMAC میں بھی استعمال ہوتا ہے) کی بنیاد پر بنایا گیا ہے: جہاں "کا مطلب ہے 'اضافی ماڈیولو'، اور۔ یہ ایک-اے۔ ڈی۔ یو۔ ہیش خاندان ہے۔ لیما 1 این ایچ کا درج ذیل ورژن ہے-اے۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔۔ کنسٹرکشن بیجر کو مضبوطی سے عالمگیریت ہیش فیملی کا استعمال کرتے ہوئے بنایا گیا ہے اور اسے اس طرح بیان کیا جا سکتا ہے جہاں ایک-اے یو یونیورسل فنکشن فیملی H * کو کسی بھی سائز کے پیغامات کو مقررہ سائز پر ہیش کرنے کے لیے استعمال کیا جاتا ہے اور ایک-اے ایس یو فنکشن فیملی F کو مجموعی تعمیر کی مضبوط عالمگیریت کی ضمانت کے لیے استعمال کیا جاتا ہے۔ NH اور ENH کا استعمال H * کی تعمیر کے لیے کیا جاتا ہے۔ فنکشن فیملی H * کا زیادہ سے زیادہ ان پٹ سائز ہے اور آؤٹ پٹ سائز 128 بٹس ہے، پیغام اور ہیش کے لیے 64 بٹس میں تقسیم کیا گیا ہے۔ H *-فنکشن کے لیے تصادم کا امکان سے لے کر تک ہوتا ہے۔ مضبوطی سے یونیورسل فنکشن فیملی F کی تعمیر کے لیے، ایک اور کلید شامل کر کے ایک مضبوط یونیورسل ہیش فیملی ایم ایم ایچ * کو ایک مضبوط یونیورسل ہیش فیملی میں تبدیل کر دیا جاتا ہے۔ بیجر پر دو مراحل ہر پیغام کے لیے دو مراحل ہوتے ہیں جن پر عمل کرنا ہوتا ہے: پروسیسنگ مرحلہ اور مرحلے کو حتمی شکل دینا۔ پروسیسنگ کا مرحلہ اس مرحلے میں، ڈیٹا کو 64 بٹ سٹرنگ میں ہیش کیا جاتا ہے۔ ایک بنیادی فنکشن: اس پروسیسنگ مرحلے میں استعمال ہوتا ہے، جو 128 بٹ سٹرنگ کو 64 بٹ سٹرنگ میں مندرجہ ذیل طور پر ہیش کرتا ہے: کسی بھی n کے لیے، اضافی ماڈیولو کا مطلب ہے۔ ایک-بٹ سٹرنگ x دیا گیا ہے، جس کا مطلب ہے کم سے کم اہم n بٹس، اور اس کا مطلب ہے سب سے اہم n بٹس۔ اس فنکشن کو استعمال کرکے پیغام پر کارروائی کی جا سکتی ہے۔ کی طرف اشارہ کریں۔ پروسیسنگ مرحلے کا سیوڈو کوڈ مندرجہ ذیل ہے۔ L = |M | اگر L = 0 حتمی شکل دینے کے لیے r = L موڈ 64 پر جائیں اگر r  ऒत्त 0: i = 1 سے u کے لیے: j = 1 سے v′ کے لیے: 64 بٹ بلاکس میں تقسیم کریں، اگر t مساوی ہے: ورنہ مرحلے کو حتمی شکل دیں۔ اس مرحلے میں، پروسیسنگ مرحلے کے نتیجے میں 64 تار کو مطلوبہ MAC ٹیگ میں تبدیل کر دیا جاتا ہے۔ حتمی شکل دینے کا یہ مرحلہ خرگوش اسٹریم سائفر کا استعمال کرتا ہے اور حتمی شکل دینے والی کلید کو لے کر کلیدی سیٹ اپ اور IV سیٹ اپ دونوں کا استعمال کرتا ہے۔ حتمی شکل دینے والے مرحلے کا سیوڈو کوڈ ربیٹکی سیٹ اپ (K) ربیٹ آئی وی سیٹ اپ (N) i = 1 سے u کے لیے: 27 بٹ بلاکس میں تقسیم کریں، S = S ′ ربیٹ نیکسٹ بٹ (u * 32) ریٹرن S نوٹیشن اوپر کے سیوڈو کوڈ سے، k خرگوش کلیدی سیٹ اپ (K) میں کلید کی نشاندہی کرتا ہے جو خرگوش کو 128 بٹ کلیدی k سے شروع کرتا ہے۔ M پیغام کو ہیش کرنے کی نشاندہی کرتا ہے اور |M بٹس میں پیغام کی لمبائی کی نشاندہی کرتا ہے۔ ایک پیغام M کی نشاندہی کرتا ہے جو i بلاکس میں تقسیم ہوتا ہے۔ دیئے گئے-بٹ سٹرنگ x کے لیے پھر اور بالترتیب اس کے سب سے کم اہم n بٹس اور سب سے اہم n بٹس کی نشاندہی کی گئی۔ پرفارمنس بوسگارڈ، کرسٹینسن اور زینر بیجر کی کارکردگی کی اطلاع دیتے ہیں جس کی پیمائش 1 گیگا ہرٹز پینٹیم III اور 1 گیگا ہرٹز پینٹیم 4 پروسیسر پر کی گئی ہے۔ اسپیڈ آپٹیمائزڈ ورژن کو اسمبلی زبان میں پروگرام کیا گیا تھا جسے سی میں ان لائن کیا گیا تھا اور انٹیل سی + + 7 کا استعمال کرتے ہوئے مرتب کیا گیا تھا۔ مندرجہ ذیل جدول مختلف محدود پیغام کی لمبائی کے لیے بیجر کی خصوصیات پیش کرتا ہے۔ "میموری ریک۔" اندرونی حالت کو ذخیرہ کرنے کے لیے درکار میموری کی مقدار کو ظاہر کرتا ہے جس میں کلیدی مواد اور خرگوش کے بہاؤ کی خفیہ شکل کی اندرونی حالت شامل ہے۔ "سیٹ اپ" کلیدی سیٹ اپ کی نشاندہی کرتا ہے، اور "فن"۔ IV-سیٹ اپ کے ساتھ حتمی شکل دینے کی نشاندہی کرتا ہے۔ ایم ایم ایچ (ملٹی لینیر ماڈیولر ہیشنگ) نام ایم ایم ایچ کا مطلب ملٹی لینیر-ماڈیولر-ہیشنگ ہے۔ ملٹی میڈیا میں ایپلی کیشنز مثال کے طور پر آن لائن ملٹی میڈیا ٹائٹل کی سالمیت کی تصدیق کے لیے ہیں۔ ایم ایم ایچ کی کارکردگی جدید مائکرو پروسیسرز میں انٹیجر اسکیلر مصنوعات کی بہتر حمایت پر مبنی ہے۔ ایم ایم ایچ اپنے سب سے بنیادی عمل کے طور پر واحد صحت سے متعلق اسکیلر مصنوعات کا استعمال کرتا ہے۔ یہ پیغام اور کلیدی ماڈیولو اے پرائم کے درمیان ایک (ترمیم شدہ) اندرونی پروڈکٹ پر مشتمل ہوتا ہے۔ ایم ایم ایچ کی تعمیر کچھ پرائم انٹیجر کے لیے محدود فیلڈ میں کام کرتی ہے۔ ایم ایم ایچ * ایم ایم ایچ * میں ہیش افعال کے ایک خاندان کی تعمیر شامل ہے جو کچھ مثبت عدد کے لیے کثیر لکیری افعال پر مشتمل ہے۔ سے لے کر تک کے افعال کے خاندان ایم ایم ایچ * کی تعریف مندرجہ ذیل ہے۔ جہاں x، m ویکٹر ہیں، اور افعال کی تعریف مندرجہ ذیل ہے۔ میک کے معاملے میں، ایک پیغام ہے اور ایک کلیدی ہے جہاں اور۔ ایم ایم ایچ * کو میک کی حفاظتی ضروریات کو پورا کرنا چاہیے، جس سے انا اور باب تصدیق شدہ طریقے سے بات چیت کر سکیں۔ ان کے پاس ایک خفیہ چابی ہے۔ کہتے ہیں کہ چارلس انا اور باب کے درمیان ہونے والی گفتگو کو سنتا ہے اور اس پیغام کو باب کو اپنے پیغام میں تبدیل کرنا چاہتا ہے جو انا کے پیغام کے طور پر منتقل ہونا چاہیے۔ لہذا، اس کا پیغام اور انا کا پیغام کم از کم ایک بٹ میں مختلف ہوگا (جیسے۔ )۔ فرض کریں کہ چارلس جانتا ہے کہ فنکشن شکل کا ہے اور وہ انا کے پیغام کو جانتا ہے لیکن وہ کلیدی x کو نہیں جانتا ہے تو اس امکان کو کہ چارلس پیغام کو تبدیل کر سکتا ہے یا اپنا پیغام بھیج سکتا ہے مندرجہ ذیل نظریہ سے سمجھایا جا سکتا ہے۔ تھیوریم 1: خاندان ایم ایم ایچ *  मुंदم-عالمگیر ہے۔ ثبوت: دو مختلف پیغامات لیں اور ہونے دیں۔ عامیت کو کھونے کے بغیر فرض کریں کہ۔ پھر کے کسی بھی انتخاب کے لیے، یہ ہے کہ اوپر دیے گئے نظریہ کی وضاحت کرنے کے لیے، پرائم کے لیے فیلڈ کو اس طرح پیش کریں۔ اگر کوئی کسی عنصر کو اندر لے جاتا ہے، تو فرض کریں کہ امکان وہ ہے۔ لیکن، اوپر دیے گئے ثبوت سے، حملہ آور کا 1 راؤنڈ میں ٹکرانے کا امکان ہے، لہذا اوسط تصدیق کے سوالات ایک پیغام کو قبول کرنے کے لیے کافی ہوں گے۔ تصادم کے امکان کو کم کرنے کے لیے، بڑے پی کا انتخاب کرنا یا آزاد چابیاں استعمال کرتے ہوئے اس طرح کے ایم اے سی کو جوڑنا ضروری ہے تاکہ تصادم کا امکان] بن جائے۔ اس صورت میں چابیاں کی تعداد میں ایک عنصر کا اضافہ ہوتا ہے اور آؤٹ پٹ میں بھی اضافہ ہوتا ہے۔ ایم ایم ایچ * 32 ہیلیوی اور کراؤزک نامی ایک قسم کی تعمیر کرتے ہیں۔ تعمیر 32 بٹ انٹیجرز اور پرائم انٹیجر کے ساتھ کام کرتی ہے۔ دراصل پرائم p کو کوئی بھی پرائم منتخب کیا جا سکتا ہے جو مطمئن کرے۔ یہ خیال کارٹر اور ویگ مین کی طرف سے پرائمز یا استعمال کرنے کی تجویز سے اپنایا گیا ہے۔ اس کی تعریف اس طرح کی گئی ہے: جہاں معنی (یعنی بائنری نمائندگی) افعال کی تعریف اس طرح کی گئی ہے۔ جہاں تھیوریم 1 کے مطابق، تصادم کا امکان تقریبا ہے، اور کے خاندان کو ε-قریب ترین  मुंदم یونیورسل کے طور پر بیان کیا جا سکتا ہے۔ k کی قدر k کی قیمت جو پیغام کی لمبائی اور کلیدی ویکٹروں کو بیان کرتی ہے اس کے کئی اثرات ہوتے ہیں: چونکہ k پر مہنگی ماڈیولر کمی کو ضرب دی جاتی ہے اور k کو بڑھانے والی کارروائیوں کو شامل کرنے سے رفتار میں کمی آتی ہے۔ چونکہ کلیدی x k 32 بٹ انٹیجرز پر مشتمل ہوتا ہے، اس لیے k کو بڑھانے کے نتیجے میں کلیدی طویل ہو جائے گی۔ نظام کو توڑنے کا امکان ہے اور اس لیے k میں اضافہ نظام کو توڑنا مشکل بنا دیتا ہے۔ کارکردگی ذیل میں 1997 میں ایم ایم ایچ کے مختلف نفاذ کے وقت کے نتائج ہیں، جسے ہیلیوی اور کراؤزک نے ڈیزائن کیا تھا۔ ایک 150 میگاہرٹز پاور پی سی 604 آر آئی ایس سی مشین جو اے آئی ایکس اے 150 میگاہرٹز پینٹیم-پرو مشین چلا رہی ہے جو ونڈوز این ٹی اے 200 میگاہرٹز پینٹیم-پرو مشین چلا رہی ہے لینکس دیکھیں یو ایم اے سی وی ایم اے سی پولی 1305-اے ای ایس حوالہ جات مضامین مثال کے طور پر سیوڈو کوڈ میسج تصدیق کوڈ کے ساتھ