RSA problem
کرپٹوگرافی میں، آر ایس اے کا مسئلہ صرف عوامی کلید کو دیکھتے ہوئے آر ایس اے پرائیویٹ کلیدی آپریشن انجام دینے کے کام کا خلاصہ پیش کرتا ہے۔ آر ایس اے الگورتھم ایک ایکسپوینٹ کے لیے ایک پیغام اٹھاتا ہے، ماڈیولو ایک جامع نمبر N جس کے عوامل معلوم نہیں ہیں۔ اس طرح، اس کام کو صاف طور پر ایک صوابدیدی نمبر، ماڈیولو این کے ایتھ روٹس کو تلاش کرنے کے طور پر بیان کیا جا سکتا ہے۔ بڑے آر ایس اے کلیدی سائز (1024 بٹس سے زیادہ) کے لیے، اس مسئلے کو حل کرنے کا کوئی موثر طریقہ معلوم نہیں ہے۔ اگر کبھی کوئی موثر طریقہ تیار کیا جاتا ہے، تو یہ آر ایس اے پر مبنی کرپٹو سسٹمز کی موجودہ یا حتمی سلامتی کو خطرہ بنائے گا-عوامی کلیدی خفیہ کاری اور ڈیجیٹل دستخط دونوں کے لیے۔ مزید خاص طور پر، آر ایس اے کا مسئلہ یہ ہے کہ ایک آر ایس اے پبلک کلید (این، ای) اور ایک خفیہ متن سی ष्ण پی ای (موڈ این) کو دیکھتے ہوئے پی کا مؤثر طریقے سے حساب لگانا ہے۔ آر ایس اے پبلک کلید کی ساخت کے لیے ضروری ہے کہ N ایک بڑا سیمی پرائم ہو (یعنی، دو بڑے پرائم نمبروں کا پروڈکٹ)، کہ 2 <e <N، کہ e کو φ (N) کا کوپرائم ہو، اور کہ 0 ≤ C <N. C کو اس حد کے اندر تصادفی طور پر منتخب کیا گیا ہے۔ مکمل درستگی کے ساتھ مسئلے کی وضاحت کرنے کے لیے، کسی کو یہ بھی بتانا چاہیے کہ N اور e کیسے تیار کیے جاتے ہیں، جو استعمال میں RSA بے ترتیب کلیدی جوڑی نسل کے عین ذرائع پر منحصر ہوگا۔ آر ایس اے کے مسئلے کو حل کرنے کے لیے جانا جانے والا سب سے موثر طریقہ ماڈیولس این کو پہلے فیکٹرنگ کرنا ہے، یہ ایک ایسا کام ہے جسے ناقابل عمل سمجھا جاتا ہے اگر این کافی بڑا ہو (انٹیجر فیکٹورائزیشن دیکھیں)۔ آر ایس اے کلیدی سیٹ اپ معمول پہلے سے ہی پبلک ایکسپونینٹ ای کو، اس پرائم فیکٹرائزیشن کے ساتھ، پرائیویٹ ایکسپونینٹ ڈی میں بدل دیتا ہے، اور اسی طرح بالکل وہی الگورتھم کسی کو بھی اجازت دیتا ہے جو نجی کلید حاصل کرنے کے لیے این کو فیکٹر کرتا ہے۔ اس کے بعد کسی بھی سی کو پرائیویٹ کلید سے ڈکرپٹ کیا جا سکتا ہے۔ جس طرح اس بات کا کوئی ثبوت نہیں ہے کہ انٹیجر فیکٹرائزیشن کمپیوٹیشنل طور پر مشکل ہے، اسی طرح اس بات کا بھی کوئی ثبوت نہیں ہے کہ آر ایس اے کا مسئلہ بھی اسی طرح مشکل ہے۔ مندرجہ بالا طریقہ کار سے، آر ایس اے کا مسئلہ کم از کم اتنا ہی آسان ہے جتنا کہ فیکٹرنگ، لیکن یہ آسان بھی ہو سکتا ہے۔ درحقیقت، اس نتیجے کی طرف اشارہ کرنے والے مضبوط شواہد موجود ہیں: کہ آر ایس اے طریقہ کار کو توڑنے کے طریقہ کار کو لازمی طور پر بڑے سیمی پرائمز کو فیکٹرنگ کے طریقہ کار میں تبدیل نہیں کیا جا سکتا۔ فیکٹرنگ اپروچ کے سراسر اوور کل سے یہ دیکھنا شاید سب سے آسان ہے: آر ایس اے کا مسئلہ ہمیں ایک من مانی خفیہ متن کو ڈکرپٹ کرنے کے لیے کہتا ہے، جبکہ حقائق کا طریقہ نجی کلید کو ظاہر کرتا ہے: اس طرح تمام صوابدیدی خفیہ متن کو ڈکرپٹ کرنا، اور یہ کسی کو من مانی آر ایس اے نجی کلیدی خفیہ کاری انجام دینے کی بھی اجازت دیتا ہے۔ ان ہی خطوط پر، ڈکرپشن ایکسپونینٹ d کو تلاش کرنا درحقیقت کمپیوٹیشنل طور پر فیکٹرنگ N کے مساوی ہے، حالانکہ RSA مسئلہ d کے لیے نہیں پوچھتا ہے۔ RSA مسئلے کے علاوہ، RSA میں ایک خاص ریاضیاتی ڈھانچہ بھی ہے جسے RSA مسئلے کو براہ راست حل کیے بغیر ممکنہ طور پر استعمال کیا جا سکتا ہے۔ آر ایس اے کے مسئلے کی مکمل طاقت کو حاصل کرنے کے لیے، آر ایس اے پر مبنی کرپٹو سسٹم کو آر ایس اے میں اس طرح کے ساختی مسائل سے بچانے کے لیے او اے ای پی جیسی پیڈنگ اسکیم کا بھی استعمال کرنا چاہیے۔ مضبوط آر ایس اے مفروضہ آر ایس اے فیکٹرنگ چیلنج رابن کرپٹو سسٹم بھی دیکھیں، جس کی فیکٹرنگ کے مساوی کو جانا جاتا ہے حوالہ جات مزید پڑھنا آر ایس اے کو توڑنا اتنا ہی مشکل ہو سکتا ہے جتنا کہ فیکٹرنگ، ڈی براؤن، 2005۔ یہ غیر ریفریڈ پری پرنٹ اس بات کا اشارہ کرتا ہے کہ سٹریٹ لائن پروگرام کا استعمال کرتے ہوئے آر ایس اے کے مسئلے کو حل کرنا اتنا ہی مشکل ہے جتنا کہ فیکٹرنگ بشرطیکہ ای کا ایک چھوٹا عنصر ہو۔ عام طور پر آر ایس اے کو توڑنا فیکٹرنگ، ڈی اگروال اور یو موریر، 2008 کے مساوی ہے۔ یہ یوروکرپٹ 2009 کا مقالہ (لنک ایک پری پرنٹ ورژن کا ہے) ثابت کرتا ہے کہ عام رنگ الگورتھم کا استعمال کرتے ہوئے آر ایس اے کے مسئلے کو حل کرنا اتنا ہی مشکل ہے جتنا کہ فیکٹرنگ۔ جب ای-تھ روٹس فیکٹرنگ سے زیادہ آسان ہو جائیں، انٹوین جوکس، ڈیوڈ ناکاچے اور ایمانوئل تھومی، 2007۔ ایشیا کرپٹ 2007 کا یہ مقالہ (لنک ایک پری پرنٹ ورژن کا ہے) ثابت کرتا ہے کہ آر ایس اے کے مسئلے کے کچھ دوسرے خاص معاملات میں اوریکل کا استعمال کرتے ہوئے آر ایس اے کے مسئلے کو حل کرنا فیکٹرنگ سے زیادہ آسان ہے۔ کمپیوٹیشنل سختی کے مفروضے پبلک کلیدی کرپٹوگرافی