Coppersmith's attack
কপারস্মিথের আক্রমণ কপারস্মিথ পদ্ধতির উপর ভিত্তি করে পাবলিক-কী ক্রিপ্টোসিস্টেম আরএসএর উপর ক্রিপ্টোগ্রাফিক আক্রমণের একটি শ্রেণী বর্ণনা করে। আর. এস. এ-কে আক্রমণ করার জন্য কপারস্মিথ পদ্ধতির বিশেষ প্রয়োগগুলির মধ্যে রয়েছে যখন সর্বজনীন সূচক ই ছোট হয় বা যখন গোপন কী-এর একটি প্রধান উপাদান সম্পর্কে আংশিক জ্ঞান পাওয়া যায়। আর. এস. এ ব্যবস্থায় পাবলিক কী হল পূর্ণসংখ্যার একটি টুপল, যেখানে এন হল দুটি মৌলিক সংখ্যা পি এবং কিউ-এর গুণফল। গোপন কীটি একটি পূর্ণসংখ্যা ডি সন্তোষজনক দ্বারা দেওয়া হয়; সমতুল্যভাবে, গোপন কীটি দ্বারা দেওয়া যেতে পারে এবং যদি চীনা অবশিষ্ট উপপাদ্যটি ডিক্রিপশনের গতি উন্নত করতে ব্যবহৃত হয়, তবে সিআরটি-আরএসএ দেখুন। একটি বার্তা এম-এর এনক্রিপশন সাইফারটেক্সট তৈরি করে, যা কম্পিউটিং ব্যবহার করে ডিক্রিপ্ট করা যেতে পারে। লো পাবলিক এক্সপোনেন্ট অ্যাটাক এনক্রিপশন বা স্বাক্ষর যাচাইয়ের সময় কমাতে, একটি ছোট পাবলিক এক্সপোনেন্ট () ব্যবহার করা দরকারী। বাস্তবে, সাধারণ পছন্দগুলি হল 3,17 এবং 65537। ই-এর জন্য এই মানগুলি হল ফার্মাট মৌলিক সংখ্যা, যা কখনও কখনও যথাক্রমে হিসাবে উল্লেখ করা হয়। এগুলি বেছে নেওয়া হয়েছে কারণ এগুলি মডুলার এক্সপোনেন্সিয়েশন অপারেশনকে দ্রুততর করে তোলে। এছাড়াও, এই ধরনের নির্বাচন করার পরে, মূল প্রজন্মের প্রথম ধাপে মৌলিক সংখ্যা তৈরি এবং পরীক্ষা করার সময় কিনা তা পরীক্ষা করা সহজ। এই পরীক্ষার যে মানগুলি ব্যর্থ হয় সেগুলি সেখানে এবং তারপরে প্রত্যাখ্যান করা যেতে পারে। (আরও ভালঃ যদি ই মৌলিক হয় এবং 2-এর চেয়ে বড় হয়, তবে পরীক্ষাটি আরও ব্যয়বহুল পরীক্ষাটিকে প্রতিস্থাপন করতে পারে।) যদি পাবলিক এক্সপোনেন্ট ছোট হয় এবং প্লেইনটেক্সট খুব ছোট হয়, তবে আরএসএ ফাংশনটি বিপরীত করা সহজ হতে পারে, যা নির্দিষ্ট আক্রমণকে সম্ভব করে তোলে। প্যাডিং স্কিমগুলি নিশ্চিত করে যে বার্তাগুলির পূর্ণ দৈর্ঘ্য রয়েছে, তবে অতিরিক্তভাবে পাবলিক এক্সপোনেন্ট নির্বাচন করার পরামর্শ দেওয়া হয়। যখন এই মানটি ব্যবহার করা হয়, তখন স্বাক্ষর যাচাইকরণের জন্য 17টি গুণন প্রয়োজন হয়, যখন একই আকারের এলোমেলো ব্যবহার করা হয় তখন প্রায় 25টির বিপরীতে। নিম্ন ব্যক্তিগত সূচকের বিপরীতে (উইনারের আক্রমণ দেখুন), যখন একটি ছোট ব্যবহার করা হয় তখন যে আক্রমণগুলি প্রযোজ্য হয় তা মোট বিরতি থেকে অনেক দূরে থাকে, যা গোপন কী পুনরুদ্ধার করবে ঘ। নিম্ন পাবলিক সূচক আরএসএর উপর সবচেয়ে শক্তিশালী আক্রমণগুলি নিম্নলিখিত উপপাদ্যের উপর ভিত্তি করে, যা ডন কপারস্মিথের কারণে হয়। কপারস্মিথ পদ্ধতি উপপাদ্য 1 (কপারস্মিথ) ধরা যাক এন একটি পূর্ণসংখ্যা এবং পূর্ণসংখ্যার উপর ডিগ্রির একটি মনিক বহুপদী। জন্য সেট করুন। তারপর, প্রদত্ত, আক্রমণকারী (ইভ) দক্ষতার সাথে সমস্ত পূর্ণসংখ্যা সন্তোষজনক খুঁজে পেতে পারে। চলমান সময়টি ও-এর মাত্রার জালিতে এলএলএল অ্যালগরিদম চালাতে যে সময় লাগে তার দ্বারা প্রভাবিত হয়। এই উপপাদ্যটি এমন একটি অ্যালগরিদমের অস্তিত্ব বর্ণনা করে যা দক্ষতার সাথে মডুলোর সমস্ত মূল খুঁজে বের করতে পারে যা তার চেয়ে ছোট। যত ছোট হয়, অ্যালগরিদমের রানটাইম হ্রাস পায়। এই উপপাদ্যের শক্তি হল বহুপদ মডুলোর সমস্ত ছোট মূল খুঁজে বের করার ক্ষমতা। হাসতাড়ের সম্প্রচার আক্রমণ হাসতাড়ের আক্রমণের সহজতম রূপটি সহজ বোঝার জন্য উপস্থাপন করা হয়েছে। সাধারণ ক্ষেত্রে কপারস্মিথ পদ্ধতি ব্যবহার করা হয়। ধরুন, একজন প্রেরক একই বার্তা এনক্রিপ্ট করা আকারে বেশ কিছু লোকের কাছে পাঠায়, প্রত্যেকে একই ছোট পাবলিক এক্সপোনেন্ট, যেমন, এবং বিভিন্ন মডুলি ব্যবহার করে। একটি সহজ যুক্তি দেখায় যে সাইফারটেক্সটগুলি জানা মাত্রই বার্তাটি আর নিরাপদ নয়ঃ ধরুন ইভ বাধা দেয়, এবং, কোথায়। আমরা সকলের জন্য অনুমান করতে পারি (অন্যথায়, গণনা করে একটি সংখ্যার গুণক গণনা করা সম্ভব)। চীনা অবশিষ্ট উপপাদ্য অনুসারে, তিনি এমনভাবে গণনা করতে পারেন। তারপর; যাইহোক, যেহেতু সবার জন্য, আমাদের আছে। এইভাবে পূর্ণসংখ্যা ধরে রাখে, এবং ইভ পাওয়ার জন্য এর ঘনমূল গণনা করতে পারে। এর বৃহত্তর মানগুলির জন্য, আরও সাইফারটেক্সট প্রয়োজন, বিশেষত, সাইফারটেক্সটগুলি যথেষ্ট। সাধারণীকরণ হেস্তাদ আরও দেখিয়েছেন যে এনক্রিপশনের আগে একটি রৈখিক প্যাডিং প্রয়োগ করা এই আক্রমণের বিরুদ্ধে সুরক্ষা দেয় না। ধরে নিন যে আক্রমণকারী জানতে পারে যে কিছু রৈখিক ফাংশনের জন্য, অর্থাৎ বব বার্তাটি এনক্রিপ্ট করার আগে একটি প্যাড প্রয়োগ করে যাতে প্রাপকরা কিছুটা ভিন্ন বার্তা পায়। উদাহরণস্বরূপ, যদি বিট দীর্ঘ হয়, বব এনক্রিপ্ট করে-তম প্রাপকের কাছে পাঠাতে পারে। যদি যথেষ্ট সংখ্যক লোক জড়িত থাকে, তবে আক্রমণকারী একই ধরনের পদ্ধতি ব্যবহার করে সমস্ত সাইফারটেক্সট থেকে প্লেইনটেক্সট পুনরুদ্ধার করতে পারে। আরও সাধারণভাবে, হ্যাস্টাদ প্রমাণ করেছিলেন যে কোনও নির্দিষ্ট বহুপদী প্রয়োগের মতো তুলনামূলকভাবে মৌলিক সংমিশ্রণে অভিন্ন সমীকরণের একটি ব্যবস্থা সমাধান করা যেতে পারে যদি পর্যাপ্ত সংখ্যক সমীকরণ সরবরাহ করা হয়। এই আক্রমণটি পরামর্শ দেয় যে আরএসএ এনক্রিপশনে র্যান্ডমাইজড প্যাডিং ব্যবহার করা উচিত। উপপাদ্য 2 (হেস্তাদ) ধরুন তুলনামূলকভাবে মৌলিক পূর্ণসংখ্যা এবং সেট। ধরা যাক সর্বাধিক মাত্রার বহুপদী। ধরুন, সকলের জন্য এক অনন্য পরিতৃপ্তি রয়েছে। উপরন্তু, অনুমান করুন। একটি দক্ষ অ্যালগরিদম রয়েছে যা সকলের জন্য দেওয়া, গণনা করে। প্রমাণ যেহেতু তুলনামূলকভাবে মৌলিক, তাই চীনা অবশিষ্ট উপপাদ্যটি সন্তোষজনক সহগ গণনা করতে এবং সকলের জন্য ব্যবহার করা যেতে পারে। সেটিং, আমরা সেটা জানি। যেহেতু এগুলি অ-শূন্য, তাই আমাদের কাছে এটিও অ-শূন্য। এর মাত্রা সর্বাধিক। কপারস্মিথের উপপাদ্য অনুসারে, আমরা সমস্ত পূর্ণসংখ্যার মূল সন্তোষজনক এবং গণনা করতে পারি। যাইহোক, আমরা জানি যে, কপারস্মিথের উপপাদ্য দ্বারা পাওয়া মূলগুলির মধ্যে এটিও রয়েছে। এই উপপাদ্যটি সম্প্রচার আর. এস. এ-র সমস্যার ক্ষেত্রে নিম্নলিখিত পদ্ধতিতে প্রয়োগ করা যেতে পারেঃ ধরুন-তম প্লেইনটেক্সটটি একটি পলিনোমিয়াল দিয়ে প্যাড করা হয়েছে, যাতে। তারপর সত্য, এবং কপারস্মিথের পদ্ধতি ব্যবহার করা যেতে পারে। আক্রমণ একবার সফল হয়, বার্তার সংখ্যা কোথায়। মূল ফলাফলটি সম্পূর্ণ কপারস্মিথ পদ্ধতির পরিবর্তে হাস্টাদের বৈকল্পিক ব্যবহার করেছিল। ফলস্বরূপ, এর জন্য বার্তার প্রয়োজন ছিল, কোথায়। ফ্রাঙ্কলিন-রেইটার সম্পর্কিত-বার্তা আক্রমণ ফ্রাঙ্কলিন এবং রেইটার আরএসএর বিরুদ্ধে আক্রমণ চিহ্নিত করেছিলেন যখন একাধিক সম্পর্কিত বার্তা এনক্রিপ্ট করা হয়ঃ যদি দুটি বার্তা শুধুমাত্র দুটি বার্তার মধ্যে একটি পরিচিত নির্দিষ্ট পার্থক্য দ্বারা পৃথক হয় এবং একই আরএসএ মডুলাসের অধীনে আরএসএ-এনক্রিপ্ট করা হয়, তবে উভয়ই পুনরুদ্ধার করা সম্ভব। আক্রমণটি মূলত পাবলিক এক্সপোনেন্টের সাথে বর্ণনা করা হয়েছিল, তবে এটি আরও সাধারণভাবে কাজ করে (ক্রমবর্ধমান খরচ সহ)। আসুন অ্যালিসের পাবলিক চাবি। ধরুন, কিছু সর্বজনীনভাবে পরিচিত বহুপদের জন্য সন্তোষজনক দুটি স্বতন্ত্র বার্তা রয়েছে। অ্যালিসকে পাঠাতে এবং পাঠাতে, বব সরলভাবে বার্তাগুলি এনক্রিপ্ট করতে পারে এবং ফলস্বরূপ সাইফারটেক্সটগুলি প্রেরণ করতে পারে। ইভ নিম্নলিখিত উপপাদ্যটি ব্যবহার করে সহজেই পুনরুদ্ধার করতে পারেঃ উপপাদ্য 3 (ফ্রাঙ্কলিন-রেইটার) একটি আরএসএ পাবলিক কী হতে দিন। কিছু রৈখিক পলিনোমিয়ালের জন্য সন্তুষ্ট করা যাক। তারপর, প্রদত্ত, আক্রমণকারী (ইভ) সময় চতুর্ভুজ মধ্যে পুনরুদ্ধার করতে পারেন। যেহেতু, আমরা জানি যে এটি পলিনোমিয়ালের মূল। একইভাবে, এর একটি মূল। সুতরাং, রৈখিক গুণক উভয় বহুপদীকে বিভক্ত করে। অতএব, ইভ এবং-এর সর্বশ্রেষ্ঠ সাধারণ ভাজক গণনা করতে পারে, এবং যদি রৈখিক বলে প্রমাণিত হয়, পাওয়া যায়। ইউক্লিডীয় অ্যালগরিদম ব্যবহার করে দ্বিঘাত সময়ে গণনা করা যেতে পারে। হেস্টাড এবং ফ্রাঙ্কলিন-রেইটারের আক্রমণের মতো কপারস্মিথের শর্ট-প্যাড আক্রমণ, এই আক্রমণটি জনসাধারণের সাথে আরএসএর দুর্বলতাকে কাজে লাগায়। কপারস্মিথ দেখিয়েছেন যে যদি হ্যাস্টাদের দ্বারা প্রস্তাবিত এলোমেলো প্যাডিং অনুপযুক্তভাবে ব্যবহার করা হয়, তবে আরএসএ এনক্রিপশন নিরাপদ নয়। ধরুন বব অ্যালিসকে এনক্রিপ্ট করার আগে একটি ছোট এলোমেলো প্যাডিং ব্যবহার করে একটি বার্তা পাঠায়। ইভ নামে একজন আক্রমণকারী সাইফারটেক্সটকে বাধা দেয় এবং এটিকে তার গন্তব্যে পৌঁছাতে বাধা দেয়। বব অ্যালিসের কাছে পুনরায় পাঠানোর সিদ্ধান্ত নেয় কারণ অ্যালিস তার বার্তায় সাড়া দেয়নি। তিনি এলোমেলোভাবে আবার প্যাড করেন এবং ফলস্বরূপ সাইফারটেক্সট প্রেরণ করেন। ইভ এখন দুটি ভিন্ন র্যান্ডম প্যাড ব্যবহার করে একই বার্তার দুটি এনক্রিপশনের সাথে সম্পর্কিত দুটি সাইফারটেক্সট রয়েছে। যদিও ইভ জানেন না যে র্যান্ডম প্যাডটি ব্যবহার করা হচ্ছে, তবুও তিনি নিম্নলিখিত উপপাদ্যটি ব্যবহার করে বার্তাটি পুনরুদ্ধার করতে পারেন, যদি র্যান্ডম প্যাডিংটি খুব ছোট হয়। উপপাদ্য 4 (কপারস্মিথ) একটি সর্বজনীন আরএসএ কী হতে হবে, যেখানে বিট দীর্ঘ। সেট করুন। সর্বাধিক বিটগুলিতে দৈর্ঘ্যের একটি বার্তা হতে দিন। এবং, কোথায় এবং এর সাথে স্বতন্ত্র পূর্ণসংখ্যাগুলি সংজ্ঞায়িত করুন। যদি ইভকে দেওয়া হয় এবং এর এনক্রিপশন দেওয়া হয় (কিন্তু দেওয়া হয় না বা), তবে সে দক্ষতার সাথে পুনরুদ্ধার করতে পারে। প্রমাণ সংজ্ঞায়িত করুন এবং। আমরা জানি যে, কখন এই পলিনোমিয়ালগুলির একটি সাধারণ মূল থাকে। অন্য কথায়, এটি ফলাফলের মূল। এছাড়াও,। অতএব, মডুলোর একটি ছোট মূল, এবং ইভ কপারস্মিথ পদ্ধতি ব্যবহার করে দক্ষতার সাথে এটি খুঁজে পেতে পারে। একবার জানা গেলে, ফ্রাঙ্কলিন-রেইটার আক্রমণ পুনরুদ্ধারের জন্য ব্যবহার করা যেতে পারে এবং ফলস্বরূপ। আরও দেখুন আরওসিএ আক্রমণ রেফারেন্স ক্রিপ্টোগ্রাফিক আক্রমণ পাবলিক-কী ক্রিপ্টোসিস্টেমের উপর আক্রমণ