Coppersmith's attack
کاپر اسمتھ کا حملہ کاپر اسمتھ طریقہ کار پر مبنی عوامی کلیدی کرپٹو سسٹم آر ایس اے پر کرپٹوگرافک حملوں کی ایک کلاس کو بیان کرتا ہے۔ آر ایس اے پر حملہ کرنے کے لیے کاپر اسمتھ طریقہ کار کی مخصوص ایپلی کیشنز میں ایسے معاملات شامل ہوتے ہیں جب پبلک ایکسپونینٹ ای چھوٹا ہوتا ہے یا جب خفیہ کلید کے پرائم فیکٹر کا جزوی علم دستیاب ہوتا ہے۔ RSA نظام میں عوامی کلید انٹیجرز کا ایک ٹپل ہے، جہاں N دو پرائمز p اور q کا پروڈکٹ ہے۔ خفیہ کلید ایک انٹیجر ڈی کے ذریعے دی گئی ہے جو تسلی بخش ہے۔ اسی طرح، خفیہ کلید اس کے ذریعے دی جا سکتی ہے اور اگر چینی ریمائنڈر تھیوریم کو ڈکرپشن کی رفتار کو بہتر بنانے کے لیے استعمال کیا جاتا ہے، تو سی آر ٹی-آر ایس اے دیکھیں۔ پیغام M کا خفیہ کاری خفیہ متن تیار کرتا ہے، جسے کمپیوٹنگ کے ذریعے ڈیکرپٹ کیا جا سکتا ہے۔ کم عوامی ایکسپونینٹ حملہ خفیہ کاری یا دستخط کی تصدیق کے وقت کو کم کرنے کے لیے، ایک چھوٹا عوامی ایکسپونینٹ () استعمال کرنا مفید ہے۔ عملی طور پر، 3، 17 اور 65537 کے لیے عام انتخاب ہیں۔ ای کے لیے یہ اقدار فرمیٹ پرائمز ہیں، جنہیں بعض اوقات بالترتیب کہا جاتا ہے۔ ان کا انتخاب اس لیے کیا جاتا ہے کیونکہ وہ ماڈیولر ایکسپونٹیشن آپریشن کو تیز کرتے ہیں۔ نیز، اس طرح کا انتخاب کرنے کے بعد، کلیدی نسل کے مرحلہ 1 میں پرائمز کو تیار کرنے اور جانچتے وقت اس کی جانچ کرنا آسان ہے۔ اس ٹیسٹ کی یا اس میں ناکام ہونے والی اقدار کو وہاں اور پھر مسترد کیا جا سکتا ہے۔ (اس سے بھی بہتر: اگر ای پرائم ہے اور 2 سے بڑا ہے، تو ٹیسٹ زیادہ مہنگے ٹیسٹ کی جگہ لے سکتا ہے۔) اگر پبلک ایکسپونینٹ چھوٹا ہے اور سادہ متن بہت چھوٹا ہے، تو آر ایس اے فنکشن کو الٹنا آسان ہو سکتا ہے، جس سے بعض حملے ممکن ہو جاتے ہیں۔ پیڈنگ اسکیمیں اس بات کو یقینی بناتی ہیں کہ پیغامات کی مکمل لمبائی ہو، لیکن اس کے علاوہ عوامی اشارے کا انتخاب کرنے کی بھی سفارش کی جاتی ہے۔ جب یہ قدر استعمال کی جاتی ہے، تو دستخطی تصدیق کے لیے 17 ضرب کی ضرورت ہوتی ہے، اس کے برعکس جب اسی سائز کا بے ترتیب استعمال کیا جاتا ہے تو تقریبا 25 کی ضرورت ہوتی ہے۔ کم پرائیویٹ ایکسپونینٹ کے برعکس (دیکھیں وینر کا حملہ)، وہ حملے جو چھوٹے استعمال ہونے پر لاگو ہوتے ہیں وہ کل وقفے سے بہت دور ہوتے ہیں، جو خفیہ کلید کو بازیافت کریں گے۔ کم عوامی ایکسپونینٹ آر ایس اے پر سب سے طاقتور حملے مندرجہ ذیل نظریہ پر مبنی ہوتے ہیں، جو ڈان کاپر اسمتھ کی وجہ سے ہوتے ہیں۔ کاپر اسمتھ طریقہ نظریہ 1 (کاپر اسمتھ) فرض کریں کہ N ایک انٹیجر ہے اور انٹیجرز پر ڈگری کا ایک مونوک کثیر الجہتی ہے۔ کے لیے سیٹ کریں۔ پھر، دیا گیا، حملہ آور (ایو) مؤثر طریقے سے تمام انٹیجرز کو تسلی بخش تلاش کر سکتا ہے۔ چلانے کے وقت پر اس وقت کا غلبہ ہوتا ہے جو طول و عرض O کے ساتھ ایل ایل ایل الگورتھم کو چلانے میں لگتا ہے۔ یہ نظریہ ایک الگورتھم کے وجود کو بیان کرتا ہے جو ماڈیولو کے ان تمام جڑوں کو مؤثر طریقے سے تلاش کر سکتا ہے جو اس سے چھوٹے ہیں۔ جیسے جیسے چھوٹا ہوتا جاتا ہے، الگورتھم کا رن ٹائم کم ہوتا جاتا ہے۔ اس تھیوریم کی طاقت کثیر الجہتی ماڈیولو کے تمام چھوٹے جڑوں کو ایک مرکب تلاش کرنے کی صلاحیت ہے۔ استاد کے نشریاتی حملے کو سمجھنے میں آسانی کے لیے استاد کے حملے کی سب سے آسان شکل پیش کی گئی ہے۔ عام کیس کاپر اسمتھ طریقہ استعمال کرتا ہے۔ فرض کریں کہ ایک بھیجنے والا ایک ہی پیغام خفیہ کردہ شکل میں متعدد لوگوں کو بھیجتا ہے، ہر ایک ایک ہی چھوٹے عوامی اشارے، جیسے، اور مختلف ماڈیولی کا استعمال کرتا ہے۔ ایک سادہ سی دلیل سے پتہ چلتا ہے کہ جیسے ہی سائفر ٹیکسٹس معلوم ہوتے ہیں، پیغام اب محفوظ نہیں رہتا ہے: فرض کریں کہ ایوا مداخلت کرتی ہے، اور، کہاں۔ ہم سب کے لیے فرض کر سکتے ہیں (بصورت دیگر، کمپیوٹنگ کے ذریعے اعداد میں سے کسی ایک کے عنصر کا حساب لگانا ممکن ہے۔) چینی بقیہ تھیوریم کے مطابق، وہ اس طرح شمار کر سکتی ہے۔ پھر ؛ تاہم، چونکہ سب کے لیے، ہمارے پاس ہے۔ اس طرح انٹیجرز کو برقرار رکھتا ہے، اور ایوا حاصل کرنے کے لیے کیوب روٹ کا حساب لگا سکتی ہے۔ کی بڑی اقدار کے لیے، مزید خفیہ متن کی ضرورت ہے، خاص طور پر، خفیہ متن کافی ہیں۔ جنرلائزیشنز ہاسٹیڈ نے یہ بھی دکھایا کہ خفیہ کاری سے پہلے لکیری پیڈنگ کا اطلاق اس حملے سے تحفظ نہیں کرتا ہے۔ فرض کریں کہ حملہ آور کو معلوم ہوتا ہے کہ کسی لکیری فنکشن کے لیے، یعنی باب پیغام کو خفیہ کرنے سے پہلے اس پر پیڈ لگاتا ہے تاکہ وصول کنندگان کو قدرے مختلف پیغامات موصول ہوں۔ مثال کے طور پر، اگر بٹس لمبا ہے، تو باب انکرپٹ کر سکتا ہے اور اسے-th وصول کنندہ کو بھیج سکتا ہے۔ اگر لوگوں کا کافی بڑا گروہ ملوث ہے، تو حملہ آور اسی طرح کے طریقوں سے تمام خفیہ متن سے سادہ متن کو بازیافت کر سکتا ہے۔ زیادہ عام طور پر، استاد نے ثابت کیا کہ غیر متغیر مساوات ماڈیولو نسبتا پرائم کمپوزائٹس کا ایک نظام، جیسے کہ کسی بھی فکسڈ کثیر الجہتی کا اطلاق، کو حل کیا جا سکتا ہے اگر کافی مقدار میں مساوات فراہم کی جائیں۔ اس حملے سے پتہ چلتا ہے کہ آر ایس اے خفیہ کاری میں بے ترتیب پیڈنگ کا استعمال کیا جانا چاہیے۔ نظریہ 2 (استاد) فرض کریں کہ نسبتا پرائم انٹیجر اور سیٹ ہیں۔ فرض کریں کہ کثیر الجہتی زیادہ سے زیادہ ڈگری کے ہوں۔ فرض کریں کہ سب کے لیے ایک منفرد اطمینان موجود ہے۔ اس کے علاوہ، فرض کریں۔ ایک موثر الگورتھم ہے جو، سب کے لیے دیا گیا ہے، حساب کرتا ہے۔ ثبوت چونکہ یہ نسبتا پرائم ہیں اس لیے چینی ریمائنڈر تھیوریم کو کوفیشنٹس کو مطمئن کرنے اور سب کے لیے شمار کرنے کے لیے استعمال کیا جا سکتا ہے۔ سیٹنگ، ہم یہ جانتے ہیں۔ چونکہ غیر صفر ہیں، ہمارے پاس وہ بھی غیر صفر ہے۔ کی ڈگری زیادہ سے زیادہ ہے۔ کاپر اسمتھ تھیوریم کے مطابق، ہم تمام انٹیجر روٹس کا حساب لگا سکتے ہیں جو مطمئن کرتے ہیں اور۔ تاہم، ہم جانتے ہیں کہ، تانبے کے نظریہ کے ذریعہ پائے جانے والے جڑوں میں سے بھی ایسا ہی ہے۔ اس تھیوریم کو براڈکاسٹ آر ایس اے کے مسئلے پر درج ذیل طریقے سے لاگو کیا جا سکتا ہے: فرض کریں کہ-th سادہ متن کو کثیر الجہتی کے ساتھ پیڈ کیا گیا ہے، تاکہ۔ پھر سچ ہے، اور کاپر اسمتھ کا طریقہ استعمال کیا جا سکتا ہے۔ حملہ ایک بار کامیاب ہو جاتا ہے، پیغامات کی تعداد کہاں ہے۔ اصل نتیجہ میں مکمل تانبے کے طریقہ کار کے بجائے استاد کا متغیر استعمال کیا گیا۔ نتیجے کے طور پر، اسے پیغامات کی ضرورت تھی، کہاں۔ فرینکلن-رائٹر سے متعلق پیغامات کے حملے فرینکلن اور رائٹر نے آر ایس اے کے خلاف حملے کی نشاندہی کی جب متعدد متعلقہ پیغامات کو خفیہ کیا جاتا ہے: اگر دو پیغامات صرف دونوں پیغامات کے درمیان معروف مقررہ فرق سے مختلف ہیں اور ایک ہی آر ایس اے ماڈیولس کے تحت آر ایس اے سے خفیہ کیے گئے ہیں، تو ان دونوں کو بازیافت کرنا ممکن ہے۔ اس حملے کو اصل میں پبلک ایکسپوینٹ کے ساتھ بیان کیا گیا تھا، لیکن یہ زیادہ عام طور پر کام کرتا ہے (بڑھتی ہوئی لاگت کے ساتھ)۔ آئیے ایلس کی عوامی کلید بنیں۔ فرض کریں کہ دو الگ الگ پیغامات ہیں جو کچھ عوامی طور پر معروف کثیر الجہتی کے لیے اطمینان بخش ہیں۔ ایلس کو بھیجنے اور بھیجنے کے لیے، باب احمقانہ طور پر پیغامات کو خفیہ کر سکتا ہے اور نتیجے میں آنے والے خفیہ متن کو منتقل کر سکتا ہے۔ ایوا مندرجہ ذیل تھیوریم کا استعمال کرتے ہوئے آسانی سے بازیافت کر سکتی ہے: تھیوریم 3 (فرینکلن-رائٹر) آئیے ایک RSA پبلک کلید بنیں۔ کچھ لکیری کثیرالجہتی کے ساتھ مطمئن کریں۔ پھر، دیا گیا، حملہ آور (ایوا) وقت میں کواڈریٹک میں صحت یاب ہو سکتا ہے۔ ثبوت چونکہ، ہم جانتے ہیں کہ یہ کثیر الجہتی کی جڑ ہے۔ اسی طرح، کی جڑ ہے۔ لہذا، لکیری عنصر دونوں کثیر الجہتی کو تقسیم کرتا ہے۔ لہذا، ایوا اور کے سب سے بڑے مشترکہ تقسیم کار کا حساب لگا سکتی ہے، اور اگر لکیری ثابت ہوتا ہے، تو پایا جاتا ہے۔ یوکلڈین الگورتھم کا استعمال کرتے ہوئے کواڈریٹک وقت میں اس کا حساب لگایا جا سکتا ہے۔ کاپر اسمتھ کا شارٹ پیڈ حملہ ہاسٹیڈ اور فرینکلن رائٹر کے حملوں کی طرح، یہ حملہ عوامی نمائندوں کے ساتھ آر ایس اے کی کمزوری کا استحصال کرتا ہے۔ کاپر اسمتھ نے دکھایا کہ اگر استاد کی تجویز کردہ بے ترتیب پیڈنگ کو غلط طریقے سے استعمال کیا جاتا ہے، تو آر ایس اے خفیہ کاری محفوظ نہیں ہے۔ فرض کریں کہ باب ایلس کو انکرپٹ کرنے سے پہلے ایک چھوٹی سی بے ترتیب پیڈنگ کا استعمال کرتے ہوئے پیغام بھیجتا ہے۔ ایک حملہ آور، ایو، خفیہ متن کو روکتا ہے اور اسے اپنی منزل تک پہنچنے سے روکتا ہے۔ باب ایلس کو دوبارہ بھیجنے کا فیصلہ کرتا ہے کیونکہ ایلس نے اس کے پیغام کا جواب نہیں دیا۔ وہ تصادفی طور پر دوبارہ پیڈ کرتا ہے اور نتیجے میں آنے والے خفیہ متن کو منتقل کرتا ہے۔ ایو کے پاس اب دو مختلف بے ترتیب پیڈ کا استعمال کرتے ہوئے ایک ہی پیغام کے دو خفیہ کاریوں کے مطابق دو خفیہ خطوط ہیں۔ اگرچہ ایوا کو معلوم نہیں ہے کہ بے ترتیب پیڈ استعمال کیا جا رہا ہے، پھر بھی وہ مندرجہ ذیل تھیوریم کا استعمال کرکے پیغام کو بازیافت کر سکتی ہے، اگر بے ترتیب پیڈنگ بہت مختصر ہے۔ نظریہ 4 (کاپر اسمتھ) ایک عوامی آر ایس اے کلید ہے، جہاں بٹس لمبا ہے۔ سیٹ کریں۔ زیادہ سے زیادہ بٹس پر لمبائی کا پیغام ہونے دیں۔ وضاحت کریں اور، کہاں اور ان کے ساتھ الگ الگ عدد ہیں۔ اگر ایوا دی جاتی ہے اور اس کی خفیہ کاری (لیکن نہیں دی جاتی ہے یا)، تو وہ مؤثر طریقے سے بازیافت کر سکتی ہے۔ ثبوت کی وضاحت کریں اور۔ ہم جانتے ہیں کہ یہ کثیر الجہتی کب مشترکہ جڑ کے طور پر ہوتے ہیں۔ دوسرے لفظوں میں، نتیجہ کی جڑ ہے۔ اس کے علاوہ،. لہذا، ماڈیولو کی ایک چھوٹی سی جڑ ہے، اور ایوا تانبے کے طریقہ کار کا استعمال کرتے ہوئے اسے مؤثر طریقے سے تلاش کر سکتی ہے۔ ایک بار معلوم ہونے کے بعد، فرینکلن-رائٹر حملے کو بازیافت اور اس کے نتیجے میں استعمال کیا جا سکتا ہے۔ مزید دیکھیں آر او سی اے حملے حوالہ جات کرپٹوگرافک حملے عوامی کلیدی کرپٹو سسٹمز پر حملے