আরএসএ গুপ্তবিদ্যা

আরএসএ

General
নির্মাতা(গণ)	রন রিভেস্ট, আদি শামির, এবং লিওনার্দ এডলমান
প্রথম প্রকাশ	১৯৭৭
স্বীকৃতি প্রদান	পিকেএস#১, আনসি এক্স৯.৩১, পি১৩৬৩
সাঙ্কেতীকরণ বিবরণ
চাবি আকারসমূহ	১,০২৪ থেকে ৪,০৯৬বিট
Rounds	১
শ্রেষ্ঠ গণ গুপ্ততত্ত্ব বিশ্লেষণ
প্রথম শ্রেণির কম্পিউটারের জন্য জেনারেল নাম্বার ফিল্ড সিভ; কোয়ান্টাম কম্পিউটারের জন্য শোরের অ্যালগোরিধম একটি ৭৬৮-বিট কি ব্রেক করা হয়েছে।

আরএসএ (রিভেস্ট–শামির–এডেলমান) হলো প্রথম দিকের পাবলিক-কি গুপ্তবিদ্যা যেটিকে নিরাপদ তথ্য প্রেরণে ব্যাপকভাবে ব্যবহৃত হয়। এই ধরনের গুপ্তবিদ্যায়, এনক্রিপশন কি পাবলিক (প্রকাশ্য) এবং একটি ডিক্রিপশন কি থাকে যেটি প্রাইভেট বা গোপন রাখা হয়। আরএসএ তে, এই পার্থক্যটি দুটি মৌলিক সংখ্যার ব্যবহারিক সমস্যার উপর নির্ভরশীল যা হলো "ফ্যাক্টরিং প্রভলেম"। আরএসএ শব্দটি রন রিভেস্ট, আদি শামির এবং লিওনার্দ এডেলমানের নামের প্রথম অক্ষর নিয়ে করা হয়েছে, যারা ১৯৭৭সালে এই অ্যালগরিধমটিকে প্রথম ব্যাখ্যা করেন। একজন ইংরেজ গণিতবিদ ক্লিফ্ফর্ড কক্স যিনি ব্রিটিশ ইন্টেলিজেন্স এজেন্সির জন্য কাজ করেন, ১৯৭৩সালে একটি দলিলে এই ধরনের পদ্ধতির বর্ণনা করেছিলেন, কিন্তু ১৯৭৭সালের পূর্বে তা প্রকাশিত হয়নি।^[১]

দুটি বড় মৌলিক সংখ্যার ভিত্তিতে একজন আরএসএ ব্যবহারকারী পাবলিক কি বানিয়ে সেটিকে প্রকাশ করে, যাদের আলাদা আরও মান থাকে। মৌলিক সংখ্যাগুলোকে গোপন রাখা হয়। যেকেউ পাবলিক কি ব্যবহার করে বার্তাকে এনক্রিপ্ট করতে পারে, আর পাবলিক কি যদি যথেষ্ট বড় হয়, তাহলে শুধুমাত্র মৌলিক সংখ্যার জ্ঞানসম্পন্ন ব্যক্তিই এই বার্তাকে ডিক্রিপ্ট করতে পারবে।^[২] আরএসএ এনক্রিপশন ব্রেক বা ভেঙ্গে ফেলাকে আরএসএ প্রভলেম বা সমস্যা বলা হয়। এটি ফ্যাক্টরিং প্রভলেমের মতো কঠিন কিনা তা আজও প্রশ্ন হিসেবে রয়ে গেছে।

আরএসএ একটু ধীর অ্যালগরিধম আর এর জন্য, সরাসরি ব্যবহারকারীর তথ্য এনক্রিপ্ট করতে এটি কম ব্যবহৃত হয়। প্রায়শই, আরএসএ সমঞ্জস সাংকেতীকরণে এনক্রিপ্টেড কি প্রেরণ করে যেটি অনেকগুলো এনক্রিপশন-ডিক্রিপশন কাজ খুব দ্রুত করতে পারে।

ইতিহাস

আদি শামির, আরএসএর তিনজন আবিষ্কারকদের একজন (অন্যান্য দুইজন রন রিভেস্ট এবং লিওনার্দ এডেলমান)

সামঞ্জস্যহীন পাবলিক-প্রাইভেট কি সাংকেতিকরণের ধারণা আসে হুইটফিল্ড ডিফি এবং মার্টিন হেলমানের কাছ থেকে, যারা এই ধারণা ১৯৭৬সালে প্রকাশ করে। তাছড়া তারা ডিজিটাল স্বাক্ষরের সূচনা করে এবং সংখ্যা তত্ত্ব ব্যবহারের প্রচেষ্টা চালায়। তাদের সূত্রে তারা একটি বিভক্ত-গোপন-কি ব্যবহার করেছে যা কিছু সাংখ্যিক সূচক ও মৌলিক সংখ্যা থেকে তৈরি। যদিও, তারা এক-পথী ফাংশন পেয়ে তারা সমস্যাটিকে সমাধান না করে রেখে দেয়, সম্ভবত এর কারণ হলো সে সময় ফ্যাক্টরিং নিয়ে তেমন গবেষণা করা হয়নি।^[৩]

রন রিভেস্ট, আদি শামির এবং লিওনার্দ এডেলমান ম্যাসাচুসেটস ইনস্টিটিউট অফ টেকনোলজিতে, একটি এক-পথী ফাংশন বানানোর জন্য এক বছর ধরে নানা প্রচেষ্টা চালায়, যেটিকে পূর্বের অবস্থায় আনা কষ্টকর হবে। কম্পিউটার বিজ্ঞানী হিসেবে, রিভেস্ট এবং শামির বিভিন্ন ফাংশনের প্রস্তাব করেন যেখানে এডেলমান গণিতবিদ হিসেবে সেসকল ফাংশনের দুর্বলতা খুঁজে বের করেন। তারা বিভিন্ন প্রচেষ্টা চালায় যার মাঝে ছিল "ন্যাপসাক" এবং "পার্মুটেশন পলিনোমিয়ালস"। কিছু সময়, পরস্পরবিরোধী চাহিদার জন্য তারা ভেবেছিল তারা যা চাচ্ছিল তা পাওয়া অসম্ভব।^[৪] ১৯৭৭সালের এপ্রিলে, তারা একজন ছাত্রের বাড়ি অবসর যাপন করে এবং মধ্যরাতে বাড়িতে ফেরার সময় তারা প্রচুর ম্যানিস্কেউইটজ মদ পান করে।^[৫] না ঘুমাতে পেরে, রিভেস্ট একটি গণিতের বই নিয়ে ছোফায় বসে এবং তাদের এক-পথী ফাংশন নিয়ে ভাবতে থাকে। সে তার ধারণা নিয়ে সারারাত কাটিয়ে দেয়, এবং বাকি কাগজগুলো সে দিনের ফাঁকে পড়ে নেয়। এই অ্যালগোরিধম আরএসএ নামে পরিচিত - তাদের নামের ক্রমানুসারে কাগজের নাম দেয়া হয়।^[৬]

একজন ইংরেজ গণিতবিদ ক্লিফ্ফর্ড কক্স যিনি ব্রিটিশ ইন্টেলিজেন্স এজেন্সির জন্য কাজ করেন, ১৯৭৩সালে একটি দলিলে এই ধরনের পদ্ধতির বর্ণনা করেছিলেন।^[৭] যদিও, এটিকে বাস্তবায়িত করার জন্য সেসময় দামী কম্পিউটারের প্রয়োজন ছিল। আরএসএ সেসময় কৌতুহলের বিষয় ছিল, আর সেসময় প্রকাশ্যে এটিকে বিস্তারিত করা হয়নি। যদিও, তার এই আবিষ্কার ১৯৯৭সালের পূর্বে এটির গোপনীয়তার জন্য প্রকাশ করা হয়নি।

কিড-আরএসএ (কেআরএসএ) হলো ১৯৯৭সালে প্রকাশিত সরল পাবলিক-কি, যা শিক্ষার উদ্দেশ্যে নকশা করা হয়। কিছু লোক মনে করে কিড-আরএসএ শেখার মাধ্যমে আরএসএ এবং অন্যান্য পাবলিক-কি গুপ্তবিদ্যা যেগুলো ডাটা এনক্রিপশন স্ট্যান্ডার্ডের অনুরূপ সেগুলো সম্পর্কে ধারণা লাভ করা যায়।^{[৮][৯][১০][১১][১২]}

পেটেন্ট

২০সেপ্টেম্বর, ১৯৮৩সালে এমআইটিকে মার্কিন পেটেন্ট ৪৪,০৫,৮২৯  প্রদান করা হয় "গুপ্ত যোগাযোগ ব্যবস্থা এবং পদ্ধতি" র জন্য যেটি এই অ্যালগরিধম ব্যবহার করে। যদিও পেটেন্টটির মেয়াদ ২১সেপ্টেম্বর, ২০০০সালে শেষ হওয়ার কথা ছিল (সেসময় পেটেন্টের মেয়াদ ছিল ১৭বছর), তবুও আরএসএ সিকিউরিটি নামে ৬সেপ্টেম্বর, ২০০০সালে, দুই সপ্তাহ পূর্বে অ্যালগরিধমটির মুক্তি দেয়া হয়।^[১৩] যেহেতু অ্যালগরিধমটির বর্ণনা ১৯৭৭সালের আগস্টে একটি কাগজে করা হয়েছে,^[৬] তাই পেটেন্টের আবেদনপত্র পূরণের তারিখ ১৯৭৭সালের ডিসেম্বরকে প্রাধান্য দিয়ে, পৃথিবীর বেশিরভাগ জায়গার নিয়ম অনুসারে এই পেটেন্টিকে নিবারণ করা হয় এবং শুধুমাত্র যুক্তরাষ্ট্রেই এটিকে গ্রহণনকরা হয়। কক্সের কাজটি জন সম্মুখে আসার পর, একটি পেটেন্ট যুক্তরাষ্ট্রেও বৈধ থাকেনা। ডারওয়েন্ট ওয়ার্ল্ড পেটেন্ট ইনডেক্স থেকে পেটেন্টির সারাংশ,

এই প্রযুক্তিতে একটি যোগাযোগ ব্যবস্থা রয়েছে যেটির এক প্রান্তে কমপক্ষে একটি এনকোডিং যন্ত্র এবং অপর প্রান্তে কমপক্ষে একটি ডিকোডিং যন্ত্র রয়েছে। একটি বার্তাকে সাংকেতিক বা গুপ্তভাবে এনকোডিং এর প্রান্তে নেয়া হয়, যেটিকে পূর্বে নির্ধারিত M সংখ্যার হিসাবে এনকোডিং করা হয়। সংখ্যাটিকে পরবর্তীতে প্রথমে নির্ধারিত ঘাতে পরিণত করা হয় (গ্রাহকের সহায়তায়) এবং সবশেষে হিসাব করা হয়। ভাগশেষ বা অবশেষ, C, কে... হিসাব করা হয় যখন পূর্বে নেওয়া দুটি মৌলিক সংখ্যার ফল দ্বারা সূচকীয় সংখ্যাটিকে ভাগ করা হয় (গ্রাহকের সহায়তায়)।

অপারেশন

আরএসএ অ্যালগরিদমে চারটি ধাপ হলো: কি জেনারেশন, কি ডিস্ট্রিবিউশন, এনক্রিপশন এবং ডিক্রিপশন।

আরএসএ-র পেছনের মূল সূত্রানুসারে তিনটি ধনাত্মক পূর্ণসংখ্যা e, d এবং n বের করতে হবে যেগুলার প্রত্যেকটির জন্য মডুলাস হবে m (যেখানে 0 ≤ m < n):

${\displaystyle (m^{e})^{d}\equiv m{\pmod {n}}}$

এখানে e এবং n অথবা m জানার পরেও d পাওয়া খুবই কষ্টসাধ্য ব্যাপার। এখানে তিনটি রেখা (≡) মডুলাসকে নির্দেশ করে।

তাছাড়া, কিছু অপারেশনের জন্য সূচকের অবস্থান পরিবর্তন করা যায় এবং সেক্ষেত্রে এই সম্পর্কটিও কাজ করে:

${\displaystyle (m^{d})^{e}\equiv m{\pmod {n}}}$

আরএসএ তে একটি পাবলিক কি এবং একটি প্রাইভেট কি থাকে। পাবলিক কি সবাইকে জানানো যায় এবং এটি বার্তা সাংকেতিকরণে বা এনক্রিপ্ট করতে ব্যবহৃত হয়। এটির উদ্দেশ্য হলো পাবলিক কি দ্বারা এনক্রিপ্ট করা বার্তাগুলো কিছু সময়ের জন্য শুধুমাত্র প্রাইভেট কি দ্বারা ডিক্রিপ্ট করা যাবে। পাবলিক কিকে n এবং e পূর্ণসংখ্যা দ্বারা নির্দেশ করা হয়; এবং প্রাইভেট কিকে d দ্বারা করা হয় (যদিও n কেও ডিক্রিপশন করার সময় ব্যবহার করা হয়। তাই এটিকেও প্রাইভেট কির অন্তর্ভুক্ত ধরা হয়)। m দ্বারা বার্তাকে বোঝানো হয় (নিম্মে বর্ণনা করা হয়েছে)।

কি জেনারেশন

নিম্মের উপায়ে আরএসএ অ্যালগরিধমের জন্য কি তৈরি করা হয়:

1. দুটি মৌলিক সংখ্যা p এবং q নেই।
   • নিরাপত্তার জন্য, p এবং q সূচক দুটিকে এলোমেলো হতে হবে, আর বিস্তার এক হলেও এগুলোকে কিছু অঙ্কে ভিন্ন হতে হবে যা ফ্যাক্টরিংকে আরও কঠিন করে দিবে।^[২] মৌলিক সূচককে মৌলিকতা পরীক্ষার মাধ্যমে সহজেই পাওয়া যায়।
   • p এবং q গোপন রাখা হয়।
2. n = pq গণনা করি।
   • n পাবলিক ও প্রাইভেট উভয় কির জন্য মডুলাস হিসেবে কাজ করে। এটির দৈর্ঘ বিট দ্বারা প্রকাশ করা হয়, যা হলে কি দৈর্ঘ্য।
   • n পাবলিক কির অংশ হিসেবে প্রকাশ করা হয়।
3. গণনা করি λ(n), যেখানে λ হলো কারমাইক্যালের টটিয়েন্ট ফাংশন। Since n = pq, λ(n) = lcm(λ(p),λ(q)), এবং যেহেতু p ও q মৌলিক সংখ্যা, λ(p) = φ(p) = p − 1 এবং একইভাবে λ(q) = q − 1. অন্যথায় λ(n) = lcm(p − 1, q − 1).
   • λ(n) গোপন রাখা হয়।
4. e একটি সূচক নির্বাচন করি যাতে 1 < e < λ(n) এবং gcd(e, λ(n)) = 1; আর, e এবং λ(n) সহমৌলিক
   • e এর বিট দৈর্ঘ্য কম এবং হ্যামিং ওজন কম হওয়ায় এটি অধিক কার্যকর এনক্রিপশন করতে পারে  – e এর জন্য ব্যবহৃত সবচেয়ে সাধারণ মান হলো 2¹⁶ + 1 = 65,537। e এর জন্য সবচেয়ে ছোট (এবং দ্রুত) মান হলো 3, কিন্তু e এর জন্য এতো ছোট মান দেখা গেছে বিশেষ ক্ষেত্রে কম নিরাপদ।^[১৪]
   • e কে মৌলিক কির অংশ হিসেবে প্রকাশ করা হয়।
5. d কে d ≡ e⁻¹ (mod λ(n)) হিসেবে ধরি; যাতে, d হলো e λ(n) এর মডুলার বিপরীত বর্ধক।
   • এর মানে: d সমীকরণের সমাধান d.e ≡ 1 (mod λ(n))। d কে ইউক্লিডীয় অ্যালগরিধম ব্যবহার করে সঠিকভাবে নির্ণয় করা যায়।
   • d কে প্রাইভেট কির অংশ হিসেবে গোপন রাখা হয়।

পাবলিক কি তে থাকে মডুলাস n এবং পাবলিক (বা এনক্রিপশন) সূচক e। প্রাইভেট কি তে থাকক প্রাইভেট (বা ডিক্রিপশন) সূচক d, যেটিকে গোপন রাখতে হয়। p, q, এবং λ(n) কেও গোপন রাখতে হয় কারণ এগুলো ব্যবহার করে d হিসাব করা যায়। উপরন্তু, d হিসাব করা হয়ে গেলক এই সবগুলোকে বাতিল করা যায়।^[১৫]

আসল আরএসএ পত্রে,^[২] প্রাইভেট সূচক d পরিামপের জন্য λ(n) এর পরিবর্তে ইউলার টটিয়েন্ট ফাংশন φ(n) = (p − 1)(q − 1) ব্যবহৃত হয়। যেহেতু φ(n) কে সবসময় λ(n) দ্বারা ভাগ করা যায় তাই এই অ্যালগরিধমও কাজ করে। যেহেতু ইউলার টটিয়েন্ট ফাংশন ব্যবহার করা যায় তাই এটিকে মডুল pq গুণফলে ল্যাগরেঞ্জ উপপাদ্য প্রয়োগের গুরুত্ব বুঝা যায়। যার কারণে d যেটি d⋅e ≡ 1 (mod φ(n)) কে মানে সেটি d⋅e ≡ 1 (mod λ(n)) কেউ মানে। যাহোক, d গণনায় মডুলো φ(n) অনেক সময় প্রয়োজনের থেকে বড় ফল দেয় (যথা d > λ(n))। যেকোন উপায় ব্যবহার করে কি তৈরি করলে আরএসএতে সেটি গৃহীত হবে (যদি পরিবর্তনশীল ডিক্রিপশন পদ্ধতি ব্যবহার না করে, তারা প্রাইভেট সূচক d ব্যবহার করে, যা নিচে বর্ণনা করা হয়েছে), কিন্তু কিছু নিয়ম যেমন এফআইপিএস ১৮৬-৪ এর ক্ষেত্রে d < λ(n) প্রয়োজন হতে পারে। যেকোন প্রাইভেট সূচক আকারে অতি বড় হলে যেটি শর্ত মানে না সেক্ষেত্রে ছোট সূচক পাওয়ার জন্য মডুলো λ(n) কে কমাতে হবে।

যেহেতু (p − 1) এবং (q − 1) এর যেকোন সাধারণ ফ্যাক্টর n − 1 = pq − 1 = (p − 1)(q − 1) + (p − 1) + (q − 1) এর ফ্যাক্টরাইজেশনে উপস্থিত,^[১৬] তাই বলা হয় (p − 1) এবং (q − 1) এর খুব ছোট সাধারণ ফ্যাক্টর রয়েছে, যদি ২এর পাশাপাশি থেকে থাকে।^{[২][১৭][১৮][১৯]}

লক্ষনীয়: মূল আরএসএ কাগজের উদ্ভাবক কি জেনারেট বা তৈরি করেন d কে চয়ন করে এবং পরে e কে d মডুলো φ(n) এর মডুলার বিপরীত গুননীয়ক হিসেনে গণনা করে, যেখানে বর্তমানের বেশিরভাগ আরএসএতে, যেমন পিকেসিএস১ এ, এটির উল্টোটা করা হয় (e চয়ন করে dকে গণনা করা হয়)। যেহেতু চয়ন কৃত কি টি ছোট হয় এবং গণনাকৃত কিটি সাধারণত ছোট হয়না, আরএসএ কাগজের অ্যালগরিধম এনক্রিপশন অনুসারে ডিক্রিপশনকে পরিবর্তন করে, যেখানে আধুনিক অ্যালগরিধম এনক্রিপশনকে পরিবর্তন করে।^{[২][২০]}

কি বিতরণ

ধরাযাক বব এলিসের কাছে তথ্য পাঠাতে চায়। তারা যদি আরএসএ ব্যবহার করতে চায়, সেক্ষেত্রে ববকে বার্তা এনক্রিপ্ট করার জন্য এলিসের পাবলিক কি জানতে হবে আর বার্তাকে ডিক্রিপ্ট করার জন্য এলিসকে তার প্রাইভেট কি ব্যবহার করতে হবে। বব যাতে এনক্রিপ্টেড বা সাংকেতিক বার্তা পাঠাতে পারে সেজন্য, এলিস তার পাবলিক কি (n, e) কোন বিশ্বাসযোগ্য মাধ্যমে প্রেরণ করে, এক্ষেত্রে গোপন হওয়ার তেমন প্রয়োজন নেই। এলিসের প্রাইভেট কি (d) কখনো বিতরণ করা হয়না।

এনক্রিপশন

বব এলিসের পাবলিক কি পাওয়ার পর, সে তার বার্তা M এলিসের কাছে পাঠাতে পারবে।

এটি করার জন্য, সে তার M (সঠিকভাবে বললে, অনাবৃত সাধারণ লেখা) কে পূর্ণসংখ্যা m (সঠিকভাবে বললে, আবৃত সাধারণ লেখা) এ রূপান্তরিত করে, যাতে 0 ≤ m < n। এর জন্য সে ব্যবহার করে প্রতিবর্তনযোগ্য একটি প্রটোকল বা নিয়ম যাকে প্যাডিং স্কিম বলা হয়। সে তারপর সাংকেতিক লেখা c কে হিসাব করে, এলিসের পাবলিক কি e ব্যবহার করে, এইভাবে মিলিয়ে

${\displaystyle c\equiv m^{e}{\pmod {n}}}$

এটি খুবই অল্প সময়ে করা যায়, বড় সংখ্যার ক্ষেত্রেও, মডুলার সূচক ব্যবহার করে। বব তারপর c কে এলিসের কাছে পাঠিয়ে দেয়।

ডিক্রিপশন

এলিস m কে পেতে পারে c থেকে তার প্রাইভেট কি d এর সাহয্যে নিচের মতো গণনা করে

${\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m{\pmod {n}}}$

এখান থেকে পাওয়া m ব্যবহার করে, সে প্যাডিং স্কিমকে আগের অবস্থায় এনে আসল বার্তা M কে পেতে পারে।

উদাহরণ

এখানে আরএসএ এনক্রিপশন এবং ডিক্রিপশনের একটি উদাহরণ দেয়া বছে। এখানে ব্যবহৃত মানগুলো কৃত্রিম ও ছোট, কিন্তু কেউ চাইলে ওপেনএসএসএল ব্যবহার করে আসল কি তৈরি করতে পারে ও পরীক্ষা করতে পারে।

1. দুটি ভিন্ন মৌলিক সংখ্যা নেই, যেমন

   ${\displaystyle p=61}$ এবং ${\displaystyle q=53}$

2. n = pq গণনা করে পাই

   ${\displaystyle n=61\times 53=3233}$

3. কারমাইক্যালের টটিয়েন্ট ফাংশন দ্বারা λ(n) = lcm(p − 1, q − 1) গণনা করে পাই

   ${\displaystyle \lambda (3233)=\operatorname {lcm} (60,52)=780}$

4. যেকোন সংখ্যা নেই 1 < e < 780 যা 780 এর সহ-মৌলিক। e এর জন্য মৌলিক সংখ্যা নিয়ে আমরা নিশ্চিত হই e 780 এর ভাজক নয়।

   এখানে ${\displaystyle e=17}$

5. d এর মডুলার বর্ধক বিপরীত e (mod λ(n)) করে পাই,

   ${\displaystyle d=413}$

   মডুলার বর্ধক বিপরীত কাজ করে এমন উদাহরণ হলো:

   ${\displaystyle d\times e=1{\bmod {\lambda }}(n)}$

   ${\displaystyle 413\times 17=1{\bmod {7}}80}$

পাবলিক কি (n = 3233, e = 17)। আবৃত সাধারণ লেখার বার্তm এর জন্য, এন্সক্রিপশন সমীকরণটি হলো

${\displaystyle c(m)=m^{17}{\bmod {3}}233}$

প্রাইভেট কি (n = 3233, d = 413)। এনক্রিপ্ট করা সাংকেতিক লেখা c এর জন্য, ডিক্রিপশন সমীকরণটি হলো

${\displaystyle m(c)=c^{413}{\bmod {3}}233}$

সংক্ষেপে, এনক্রিপ্ট করার জন্য m = 65, আমরা হিসাব করি

${\displaystyle c=65^{17}{\bmod {3}}233=2790}$

ডিক্রিপ্ট করার জন্য c = 2790, আমরা হিসাব করি

${\displaystyle m=2790^{413}{\bmod {3}}233=65}$

মডুলার সূচকের জন্য বর্গ এবং গুণের অ্যালগোরিধম ব্যবহার করে এই দুটি গণনা হিসাব করা যায়। বাস্তব জীবনে মৌলিক সংখ্যাগুলো আরও বড় হবে; আমাদের উদাহরণে ফ্যাক্টর n এর কাছে যা নগন্য, 3233 (মুক্ত পাবলিক কি হতে পাওয়া) থেকে p এবং q দুটি মৌলিক সংখ্যা পাওয়া যায়। e, ও পাবলিক কি থেকে পাওয়া, যেটিকে পরে d তে রূপান্তরিত করা হয়, এইভাবে প্রাইভেট কি পাওয়া যায়।

ফ্যাক্টরে মডুলাস ব্যবহার করে গণনার কাজ দ্রুত করার জন্য বাস্তব জীবনে চীনা রীমাইন্ডার থিয়োরি ব্যবহার করা হয় (মডুলাস 'p' এবং 'q' ব্যবহার করে মডুলাস 'pq')।

d_p, d_q এবং q_inv এর মানগুলো, যেগুলো প্রাইভেট কির অন্তর্ভুক্ত নিম্নানুসারে গণনা করা হয়:

${\displaystyle {\begin{aligned}d_{p}={}&d{\bmod {(}}p-1)=413{\bmod {(}}61-1)=53\\d_{q}={}&d{\bmod {(}}q-1)=413{\bmod {(}}53-1)=49\\q_{\text{inv}}={}&q^{-1}{\bmod {p}}=53^{-1}{\bmod {6}}1=38\\\Rightarrow {}&(q_{\text{inv}}\times q){\bmod {p}}=38\times 53{\bmod {6}}1=1\end{aligned}}}$

নিম্নানুসারে d_p, d_q এবং q_inv কার্যকরী ডিক্রিপশনে ব্যবহার করা হয়। (কার্যকর d এবং e যুগল ব্যবহার করে কার্যকর এনক্রিপশন করা যায়)

${\displaystyle {\begin{aligned}m_{1}&=c^{d_{p}}{\bmod {p}}=2790^{53}{\bmod {6}}1=4\\m_{2}&=c^{d_{q}}{\bmod {q}}=2790^{49}{\bmod {5}}3=12\\h&=(q_{\text{inv}}\times (m_{1}-m_{2})){\bmod {p}}=(38\times -8){\bmod {6}}1=1\\m&=m_{2}+h\times q=12+1\times 53=65\end{aligned}}}$

কোড

এটি হলো জাবাস্ক্রিপ্টে BigInteger.js ব্যবহার করে একটি কার্যকর উদাহরণ। এই কোডটি উৎপাদনে ব্যবহার করা যাবেনা। কারণ bigInt.randBetween() Math.random() ব্যবহার করে, যেটি নিরাপদ সাংকেতিকরণের ছদ্ম সংখ্যা উৎপাদক নয়।^[২১]

'use strict';

/**
* RSA hash function reference implementation.
* Uses BigInteger.js https://github.com/peterolson/BigInteger.js
* Code originally based on https://github.com/kubrickology/Bitcoin-explained/blob/master/RSA.js
*/
const RSA = {};

/**
* Generates a k-bit RSA public/private key pair
* https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Code
*
* @param {keysize} int, bitlength of desired RSA modulus n (should be even)
* @returns {array} Result of RSA generation (object with three bigInt members: n, e, d)
*/
RSA.generate = function(keysize) {
/**
* Generates a random k-bit prime greater than √2 × 2^(k-1)
*
* @param {bits} int, bitlength of desired prime
* @returns {bigInt} a random generated prime
*/
function randomPrime(bits) {
const min = bigInt(6074001000).shiftLeft(bits - 33); // min ≈ √2 × 2^(bits - 1)
const max = bigInt.one.shiftLeft(bits).minus(1); // max = 2^(bits) - 1
for (;;) {
const p = bigInt.randBetween(min, max); // WARNING: not a cryptographically secure RNG!
if (p.isProbablePrime(256)) {
return p;
}
}
}

// set up variables for key generation
const e = bigInt(65537); // use fixed public exponent
let p;
let q;
let lambda;

// generate p and q such that λ(n) = lcm(p − 1, q − 1) is coprime with e and |p-q| >= 2^(keysize/2 - 100)
do {
p = randomPrime(keysize / 2);
q = randomPrime(keysize / 2);
lambda = bigInt.lcm(p.minus(1), q.minus(1));
} while (bigInt.gcd(e, lambda).notEquals(1) || p.minus(q).abs().shiftRight(
keysize / 2 - 100).isZero());

return {
n: p.multiply(q), // public key (part I)
e: e, // public key (part II)
d: e.modInv(lambda), // private key d = e^(-1) mod λ(n)
};
};

/**
* Encrypt
*
* @param {m} int / bigInt: the 'message' to be encoded
* @param {n} int / bigInt: n value returned from RSA.generate() aka public key (part I)
* @param {e} int / bigInt: e value returned from RSA.generate() aka public key (part II)
* @returns {bigInt} encrypted message
*/
RSA.encrypt = function(m, n, e) {
return bigInt(m).modPow(e, n);
};

/**
* Decrypt
*
* @param {c} int / bigInt: the 'message' to be decoded (encoded with RSA.encrypt())
* @param {d} int / bigInt: d value returned from RSA.generate() aka private key
* @param {n} int / bigInt: n value returned from RSA.generate() aka public key (part I)
* @returns {bigInt} decrypted message
*/
RSA.decrypt = function(c, d, n) {
return bigInt(c).modPow(d, n);
};

বার্তা স্বাক্ষর

ধরি এলিস ববের পাবলিক কি ব্যবহার করে তাকে এনক্রিপ্টেড বা সাংকেতিক বার্তা প্রেরণ করবে। বার্তায়, সে এলিস হিসেবে দাবি করতে পারে কিন্তু ববের কাছে কোন উপায় নেই তা নিশ্চিত করার যে সেই বার্তাটি এলিস পাঠিয়েছে। কারণ যেকেও ববের পাবলিক কি ব্যবহার করে তাকে বার্তা প্রেরণ করতে পারে। বার্তার প্রেরককে নিশ্চিত করতে, আরএসএকে কোন বার্তায় স্বাক্ষর (ডিজিটাল স্বাক্ষর) করতেও ব্যবহার করা যেতে পারে।

ধরি এলিস ববের কাছে স্বাক্ষরিত বার্তা প্রেরণ করতে চায়। সে তার নিজের প্রাইভেট কি ব্যবহার করে এটি করতে পারে। সে বার্তাটির একটি হ্যাশ (সাংকেতিক হ্যাশ ফাংশন) মান তৈরি করে, তারপর এটিকে d (মডুলো n) এর ঘাতে পরিণত করে (যেমনটি সে বার্তাকে ডিক্রিপ্ট করতে ব্যবহার করে), আর এটিকে "স্বাক্ষর" হিসেবে বার্তায় যুক্ত করে। বব যখন স্বাক্ষরিত বার্তাটি পায়, সে এলিসের পাবলিক কি দিয়ে একই হ্যাশ অ্যালগরিধম ব্যবহার করে। সে স্বাক্ষরকে e (মডুলো n) এর ঘাতে পরিণত করে(যেমনটি সে বার্তা এনক্রিপ্ট করার সময় করে), এবং সেখান থেকে পাওয়া হ্যাশ মানের সাথে বার্তার হ্যাশ মানের তুলনা করে। যদি দুটি মিলে, সে বুঝতে পারে বার্তাটি এলিসের প্রাইভেট কি ব্যবহার করে প্রেরিত এবং বার্তাটি তারপর থেকে পরিবর্তিত হয়নি।

এটি কাজ করে কারণ গুন হলো বিনিময়যোগ্য তাই ${\displaystyle h=hash(m);(h^{e})^{d}=h^{ed}=h^{de}=(h^{d})^{e}\equiv h{\pmod {n}}}$ তাই, কিগুলোর মানের কোন হ্রাস না করেই কিগুলোকে অদল বদল করা যায়। কিযুগলের একটি প্রাইভেট কিকে ব্যবহার করা যায়:

1. প্রাপকের জন্য বার্তা ডিক্রিপ্ট করতে, যেটিকে পাবলিক কি (অসামঞ্জস্য এনক্রিপ্টেড) থাকা যেকেও এনক্রিপ্ট করতে পারবে।
2. একটি বার্তাকে এনক্রিপ্ট করতে যা যেকেও ডিক্রিপ্ট করতে পারে, কিন্তু শুধুমাত্র একজন লোক সেটি এনক্রিপ্ট করতে পারবে (স্বাক্ষর)।

প্যাডিং

সরল আরএসএর বিরুদ্ধে আক্রমণ

নিচের বর্ণানুযায়ি সরল আরএসএর বিরুদ্ধে নানা আক্রমণ রয়েছে।

• নিম্ন এনক্রিপশন সূচক নিয়ে এনক্রিপশন করার সময় (যেমনe = 3) এবং m এর নিম্ন মানের সময়, (i.e., m < n^1/e) m^e এর মান মডুলাস n থেকে কম হয়। এক্ষেত্রে, পূর্ণসংখ্যাকে গুপ্তবার্তার eতম রুট করে গুপ্তবার্তাকে খুব সহজেই ডিক্রিপ্ট করা যায়।
• যদি একই বার্তা e বা একাধিক গ্রাহকের কাছে এনক্রিপ্ট পদ্ধতিতে পাঠানো হয়, এবং গ্রাহকদের একই সূচক e, কিন্তু ভিন্ন ভিন্ন different p, q, আর n থাকে, তাহলে চীনা ভাগশেষ উপপাদ্য দিয়ে মূল বার্তাকে ডিক্রিপ্ট করা যায়। জোহান হাস্তাদ খেয়াল করেন এই আক্রমণটি করা যায় যদি বার্তা এক নাও হয় কিন্তু আক্রমণকারী তাদের মাঝের দৈর্ঘ্যের পার্থক্য বুঝতে পারে।^[২২] এই আক্রমণ পরবর্তীতে উন্নয়ন করেন ডন কপারস্মিথ।^[২৩]

আরও দেখুন: Coppersmith's Attack

• যেহেতু আরএসএ এনক্রিপশন হলো নির্ণায়ক অ্যালগরিদম(কোন এলোমেলো সূচক নেই) তাই একজন আক্রমণকারী সফলভাবে এই গুপ্তবিদ্যায় সরলবার্ত আক্রমণ চালাতে পারে, যার জন্য সে পাবলিক কি ব্যবহার করে সরলবার্তাকে এনক্রিপ্ট করবে এবং পরে পরীক্ষা করবে যেন সেগুলো গুপ্তবার্তার সমান হয়। একটি গুপ্তবিদ্যাকে শাব্দিকভাবে নিরাপদ বলা হয় যদি একজন আক্রমণকারী সরলবার্তা জানার পরেও দুটি এনক্রিপশন জানতে না পারে। উপরের বর্ণনানুসারে, প্যাডিং বা আবরণ ছাড়া আরএসএ শাব্দিকভাবে নিরাপদ নয়।^[২৪]
• আরএসএর একটি বৈশিষ্ট্য হলো দুটি গুপ্তবার্তার গুণফল যথাক্রমে দুটি সরলবার্তার এনক্রিপশনের গুণফলের সমান হয়। যা হলো m₁^em₂^e ≡ (m₁m₂)^e (mod n)। এই গুণফলের বৈশিষ্ট্যের জন্য একটি গুপ্তবার্তা আক্রমণ করা যায়। যেমন, একজন আক্রমণকারী যে গুপ্তবার্তা c ≡ m^e (mod n) এর ডিক্রিপশন জানতে চায়, সে প্রাইভেট কি d ধারীকে একটি সন্দেহহীন দেখতে গুপ্তবার্তা c′ ≡ cr^e (mod n) কে ডিক্রিপ্ট করার জন্য বলতে পারে, আক্রমণকারীর নির্ধারিত r এর কিছু মান পাওয়ার জন্য। এই গুণফলের বৈশিষ্ট্যের কারণে c′ হলো mr (mod n) এর এনক্রিপশন। আবার, যদি আক্রমণকারী এই আক্রমণে সফল হয় সে জানতে পারবে mr (mod n) যেখান থেকে সে বার্তা m কে পেতে পারে, mr কে r মডুল n এর মডুল বিপরীতের সাথে গুণ করে।^{[তথ্যসূত্র প্রয়োজন]}

প্যাডিং নকশা

এই সমস্যাগুলো এড়াতে, ব্যবহারিক আরএসএতে m কে এনক্রিপ্ট করার আগে এটিতে বিশেষ গঠনের, এলোমেলো প্যাডিং যুক্ত করা হয়। এই প্যাডিং নিশ্চিত করে যে m অনিরাপদ বার্তা নয়, আর কোন বার্তা প্যাডিং করা থাকলে সেটি সম্ভাব্য অসংখ্য গুপ্তবার্তায় এনক্রিপ্ট হবে।

আরএসএ এনক্রিপশনে বার্তাকে নিরাপদে প্যাড বা আব্রিত করার জন্য পিকেসিএস১ কে নকশা করা হয়েছে। যেহেতু এই নকশা সরল বার্তা m কে কিছু বিট যুক্ত করে প্যাড করে, তাই প্যাড করা বার্তা হতে প্যাডহীন বার্তা M আকারে ছোট হয়। আরএসএ প্যাডিং নকশাকে সাবধানে তৈরি করতে হয় যাতে কঠিন কোন আক্রমণ থেকে বাঁচা যায় যেগুলো বার্তার গঠনকে অনুমান করে করা যেতে পারে। পিকেসিএস#১ এর প্রথম সংস্করণগুলো (১.৫ সংস্করণ পর্যন্ত) একটি গঠন ব্যবহার করতো যেটি আরএসএকে শাব্দিকভাবে নিরাপদ করত। যদিও, ১৯৯৮ আন্তর্জাতিক ক্রিপ্টোলোজি কনফারেন্সে, ব্লেইচেনবেকার দেখান যে এই সংস্করণটি ব্যবহারিক এডাপ্টিভ চোজেন সাইফারটেক্সট আক্রমণের সামনে খুব দুর্বল। আরও, ২০০০সালে ইউরোক্রিপ্টে, করোন এট আল.^{[তথ্যসূত্র প্রয়োজন]} দেখান যে কয়েক ধরনের বার্তার জন্য, এই প্যাডিং উচ্চ মানের নিরাপত্তা প্রদান করেনা। এটির পরবর্তী সংস্করণে অপটিমাল এসিমেট্রিক এনক্রিপশন প্যাডিং যুক্ত করা হয় যা এই ধরনের আক্রমণকে প্রতিরোধ করে। এজন্য, যেকোন নতুন এপ্লিকেশনে ওআইপি ব্যবহার করতে হবে এবং পিকেসিএস#১ ১.৫সংস্করণ দ্বারা প্রতিস্থাপিত করতে হবে। পিকেসিএস#১ নকশাতে আরএসএ স্বাক্ষরে অতিরিক্ত নিরাপত্তার জন্য আলাদা নকশা অন্তর্ভুক্ত করা হয়েছে, যেমন আরএসএর জন্য সম্ভাব্য স্বাক্ষর নকশা(আরএসএ-পিএসএস)।

নিরাপদ প্যাডিং নকশা যেমন আরএসএ-পিএসএস বার্তা স্বাক্ষরে নিরাপত্তার জন্য খুব প্রয়োজনীয় কারণ এগুলো বার্তাকে এনক্রিপ্ট করতে ব্যবহৃত হয়। পিএসএস এর দুটি যুক্তরাষ্ট্র পেটেন্ট গৃহীত হয় (ইউএসপিটিও ৬২৬৬৭৭১ এবং ইউএসপিটিও ৭০৩৬০১৪০); যদিও, এই পেটেন্টগুলো ২০০৯সালের ২৪জুলাই এবং ২০১০সালের ২৫এপ্রিলে মেয়াদোত্তীর্ণ হয়ে যায়। পিএসএস এর ব্যবহারে এখন আর পেটেন্ট দ্বারা করা হয়না। লক্ষনীয় যে এনক্রিপ্ট করা এবং স্বাক্ষর করার জন্য বিভিন্ন আরএসএ-কি যুগল ব্যবহার করা অনেক বেশি নিরাপদ।^[২৫]

নিরাপত্তা ও ব্যবহারিক আলোচনা

চীনা ভাগশেষ অ্যালগরিধমের ব্যবহার

কার্যকারীতার জন্য অনেক জনপ্রিয় গুপ্তবিদ্যার লাইব্রেরি (যেমন ওপেনএসএসএল, জাবা এবং. নেট) ডিক্রিপশন এবং স্বাক্ষর করতে চীনা ভাগশেষ উপপাদ্য ব্যবহার করে। নিম্নের মানগুলো পূর্বেহিসাব করা হয় এবং প্রাইভেট কির অংশ হিসেবে জমা রাখা হয়:

• ${\displaystyle p}$ এবং ${\displaystyle q}$: কি তৈরির সময়কার মৌলিক সংখ্যাগুলো,
• ${\displaystyle d_{P}=d{\pmod {p-1}}}$,
• ${\displaystyle d_{Q}=d{\pmod {q-1}}}$ এবং
• ${\displaystyle q_{\text{inv}}=q^{-1}{\pmod {p}}}$।

এই মানগুলো সূচকের হিসাব m = c^d (mod pq) গ্রাহককে আরও কার্যকরীভাবে করতে সাহায্য করে:

• ${\displaystyle m_{1}=c^{d_{P}}{\pmod {p}}}$
• ${\displaystyle m_{2}=c^{d_{Q}}{\pmod {q}}}$
• ${\displaystyle h=q_{\text{inv}}(m_{1}-m_{2}){\pmod {p}}}$ (যদি ${\displaystyle m_{1}<m_{2}}$ তাহলে কিছু লাইব্রেরি h কে ${\displaystyle q_{\text{inv}}\left[\left(m_{1}+\left\lceil {\frac {q}{p}}\right\rceil p\right)-m_{2}\right]{\pmod {p}}}$ হিসাবে গণনা করে)
• ${\displaystyle m=m_{2}+hq\,}$

যদিও দুটি সূচকীয় মডুলার হিসাব করতে হয়, তবুও এটি সূচকীয় বর্গ করা থেকে বেশি কার্যকরি। কারণ এই দুটি সূচকীয় মডুলারের উভয়টিতে ছোট সূচক ও ছোট মডুলাস থাকে।

পূর্নসংখ্যার ফ্যাক্টর এবং আরএসএ সমস্যা

আরএসএ গুপ্তবিদ্যা দুটি গাণিতিক সমস্যার উপর নির্ভরশীল: পূর্ণসংখ্যার ফ্যাক্টর এবং আরএসএ সমস্যা। আরএসএ গুপ্ত বার্তার সম্পূর্ণ ডিক্রিপশনকে অসম্ভব হিসেবে মনে করা হয় কারণ উভয় সমস্যাটি খুব কঠিন, কারণ এগুলো সমাধান করার জন্য কোন কার্যকরী অ্যালগরিধম নেই। অসম্পূর্ণ ডিক্রিপশনে নিরাপত্তা প্রদানের জন্য একটি নিরাপদ প্যাডিং বা আবরণের প্রয়োজন হতে পারে।^[২৬]

আরএসএ সমস্যা হলো eতম রুটের n: m এর যোগ যার একটি এমনভাবে বের করা যাতে c ≡ m^e (mod n), যেখানে (n, e) হলো একটি আরএসএ পাবলিক কি এবং c হলো আরএসএ গুপ্তলেখা। বর্তমানে মডুলাস n এর ফ্যাক্টর করাই হলে আরএসএ সমস্যা সমাধানের সেরা উপায়। মৌলিক ফ্যাক্টরগুলো পাওয়ার মাধ্যমে, একজন আক্রমণকারী পাবলিক কি (n, e) হতে গোপন সূচক d কে হিসাব করতে পারে, তারপর c কে সাধারণ উপায়ে ডিক্রিপ্ট করতে পারবে। এটি করার জন্য, একজন আক্রমণকারী p এবং q তে n কে ফ্যাক্টর করে, আর lcm(p − 1, q − 1) গণনা করে যার মাধ্যমে e হতে d কে জানা যায়। সাধারণ কম্পিউটারে বড় পূর্ণসংখ্যার ফ্যাক্টর করার জন্য কোন পলিনমিয়াল-সময় পদ্ধতি পাওয়া যায়নি, কিন্তু এটির যে অস্তিত্ত্ব নেই তা প্রমাণিত নয়।

পাবলিক মডুলাস n কে ফ্যাক্টর করার জন্য মাল্টিপল পলিনমিয়াল কোয়াড্রেটিক সিভ (এমপিকিউএস) ব্যবহার করা যায়। একটি ডেস্কটপ কম্পিউটারে (প্রসেসর: ইন্টেল ডুয়েল-কোর আই৭-৪৫০০ইউ ১.৮০গিগাহার্জ) ১২৮-বিট এবং ২৫৬-বিট n কে ফ্যাক্টর করতে প্রয়োজনীয় সময় হলো যথাক্রমে ২সেকেন্ড এবং ৩৫মিনিট।

বিট	সময়
১২৮	২ সেকেন্ড থেকে কম
1১৯২	১৬ সেকেন্ড
২৫৬	৩৫ মিনিট
২৬০	১ ঘণ্টা

^{[মৌলিক গবেষণা?]}

ইয়াফু নামক সফটওয়্যার ব্যবহার করে এই পদ্ধতিকে কার্যকরী করা যায়।^[২৭] এটি একই কম্পিউটারে ৩২০বিট-n কে ফ্যাক্টর করতে ৫৭২০সেকেন্ড নিয়েছে।

বিট	সময়	ব্যবহৃত মেমোরি
১২৮	0.৪৮৮৬ সেকেন্ড	০.১ MiB
১৯২	৩.৯৯৭৯ সেকেন্ড	০.৫ MiB
২৫৬	১০৩.১৭৪৬ সেকেন্ড	৩ MiB
৩০০	১১৭৫.৭৮২৬ সেকেন্ড	১০.৯ MiB

২০০৯সালে, বেন্জামিন মুডি আরএসএ-৫১২ বিট কিকে ৭৩দিনে ফ্যাক্টর করেছেন শুধুমাত্র উন্মুক্ত সফটওয়্যার (জিজিএনএফএস) এবং তার ডেস্কটপ কম্পিউটার (একটি ডুয়েল-কোর এথলোন৬৪ সাথে একটি ১,৯০০মেগাহার্জ সিপিইউ) ব্যবহার করে। পাঁচ গিগাবাইটেরও কম মেগাবাইট ডিস্ক স্টোরেজ এবং মাত্র ২.৫গিগাবাইট র্যাম এই কাজে ব্যবহৃত হয়। প্রথম আরএসএ-৫১২ ফ্যাক্টর করতে ৮,৪০০ এমআইপিএস বছর লেগেছিল, যেটিতে প্রায় ৭মাস সময় লাগে।^{[২৮][ভালো উৎস প্রয়োজন]}

রিভেস্ট, শামির এবং এডেলমান উল্লেখ করেন^[২] যে মিলার রিমানের অনুমানের উপর বিশ্বাস করে দেখিয়েছেন- n এবং e থেকে d বের করা n কে p এবং q এর মাঝে ফ্যাক্টরিং করার মতোই কঠিন(সময়ের ব্যবধানে)।^[২৯] যায়হোক, রিভেস্ট, শামির এবং এডেলমান তাদের পত্রের IX/D অংশে বিবৃত করেন যে, আরএসএ কে পূর্বের অবস্থায় ফিরিয়ে আনা যে আরএসএ কে ফ্যাক্টর করার মতোই কঠিন তার কোন প্রমাণ তারা পাননি।

২০১০সাল অনুযায়ী, আরএসএ সংখ্যার ফ্যাক্টর করা সবচেয়ে বড় সংখ্যাটি ৭৬৮ বিট দীর্ঘ ছিল (২৩২ ডেসিমাল ডিজিট বা অঙ্ক)। তখনকার প্রযুক্তি অনুসারে এটির ফ্যাক্টরাইজেশন করতে, ১৫০০কম্পিউটারের কয়েক বছর সময় লেগেছিল (দুই বছর, অনেকগুলল কম্পিউটারের সাহায্যে)। এর চেয়ে বড় আরএসএ কির ফ্যাক্টর এখনও করা যায়নি। ব্যবহারিকভাবে, আরএসএ কি ১০২৪ থেকে ৪০৯৬ বিট দীর্ঘ হয়। কিছু বিশেষজ্ঞ মনে করেন ১০২৪-বিট হয়তো ভবিষ্যতে ব্রেক করা যাবে বা হয়তো যথেষ্ট উপকরণ থাকলে আক্রমণকারীরা এখনই ব্রেক করতে পারবে, যদিও এটি বিতর্কিত। কিছু লোক দেখেন যে ৪০৯৬ বিট কিগুলো সুদূর ভবিষ্যতে ব্রেক করা যাবে। এইজন্য, ধরা হয় আরএসএ নিরাপদ যদি n যথেষ্ট বড় হয়। যদি n ৩০০বিট বা তার চেয়ে ছোট হয়, এটিকে ব্যক্তিগত কম্পিউটারে কয়েক ঘণ্টাতেই ফ্যাক্টর করা যাবে, উন্মুক্ত সফটওয়্যার ব্যবহার করে। ৫১২বিটের কিগুলো ব্যবহারিকভাবে ব্রেক করে দেখানো হয় ১৯৯৯সালে যখন শত শত কম্পিউটার ব্যবহার করে আরএসএ-১৫৫ কে ফ্যাক্টর করা হয়, আর বর্তমানে এগুলো সাধারণ হার্ডওয়্যার ব্যবহার করে কিছু সপ্তাহেই ফ্যাক্টর করা যায়। ২০১১সালে, ৫১২-বিটের কোড-সাইনিং সার্টিফিকেট ব্যবহার করে এমন এক্সপ্লোয়েটগুলোকে (যেগুলো হয়তো ফ্যাক্টর করা হয়েছে) বাতিল করা হয়।^[৩০] ২০০৩সালে, শামির এবং ট্রোমারের বর্ণনা করা, টুইর্ল নামক এক তাত্ত্বিক যন্ত্র ১০২৪ বিটের কির নিরাপত্তা নিয়ে প্রশ্ন তুলে। বর্তমানে কিকে ২০৪৮ বিট দীর্ঘ হওয়ার পরামর্শ দেয়া হয়।^[৩১]

১৯৯৪সালে, পিটার শোর দেখান যে একটি কোয়ান্টাম কম্পিউটার - যদি কেউ ব্যবহারিকভাবে এই উদ্দেশ্যে বানাতে পারে - আরএসএ ব্রেক করার জন্য পলিনমিয়াল সময়ে (অ্যালগরিধম চলানোর জন্য যে সময় লাগে) ফ্যাক্টর করতে পারবে।

ত্রুটিপূর্ণ কি তৈরি

মৌলিক সংখ্যা p এবং q খুঁজে বের করা হয় কিছু সঠিক আকারের এলোমেলো সংখ্যা থেকে মৌলিকতা পরীক্ষা করে যেটি কাল্পনিকভাবে অমৌলিক সংখ্যাগুলোকে বাদ দিয়ে দেয়।

p এবং q সংখ্যা দুটি "খুব কাছাকাছি" হওয়া নেয়া যাবেনা, যাতে n এর জন্য ফারমেট ফ্যাক্টরিয়াজেশন সফল হয়। যদি p − q, 2n হতে ছোট হয়^1/4 (n = p * q, which for even small 1024-bit values of n is ৩×১০^৭৭) p এবং q এর মান তুচ্ছ বা সামান্য হবে। উপরন্তু, যদি p − 1 বা q − 1 এর যেকোন একটির ছোট মৌলিক ফ্যাক্টর থাকে, তবে n এর ফ্যাক্টর পোলারের p − 1 অ্যালগরিধম দিয়ে বের করা যাবে, আর p বা q এর মানগুলো বাদ দেয়া যাবে।

প্রাইভেট কির অংশ d কে যথেষ্ট বড় হতে হয়। মাইকেল জে. ওয়েইনার দেখান যে যদি p, q এবং 2q এর মাঝে হয় (যেটি সাধারণ) এবং d < n^1/4/3, তাহলে d কে n এবং e থেকে গণনা করে বের করা যায়।^[৩২]

ছোট পাবলিক সূচক যেমন e = 3 এর বিরুদ্ধে কোন আক্রমণ করা হয়না, কারণ এটিতে সঠিক আবরণ বা প্যাডিং ব্যবহৃত হয়েছে। কপারস্মিথ আরএসএ তে বিভিন্ন আক্রমণ চালান বিশেষ করে যদি পাবলিক সূচক e ছোট হয় এবং যদি এনক্রিপ্টেড বার্তা ছোট হয় এবং আবৃত না হয়। ৬৫৫৩৭ হলো e এর জন্য ব্যবহৃত একটি সাধারণ মান; এই মানটি ছোট সূচক আক্রমণ প্রতিরোধ করার একটি ব্যবস্থা যা পর্যাপ্ত এনক্রিপশন (বা স্বাক্ষর পরীক্ষা) করার সুযোগ দপয়। কম্পিউটারের নিরাপত্তা নিয়ে দ্যা এনআইএসটি বিশেষ প্রকাশন (এসপি ৮০০-৭৮ রেভ আগস্ট ১ ২০০৭) পাবলিক সূচক e কে ৬৫৫৩৭এর থেকে ছোট হওয়া মেনে নেয়না, কিন্তু এই নিষেধাজ্ঞার কোন কারণ উল্লেখ করেনা।

২০১৭সালের অক্টোবরে, মাজারিক বিশ্ববিদ্যালয়ের এক দল গবেষক রোকা দুর্বলতা ঘোষণা করেন, যা মূলত ইনফিনেয়ন লাইব্রেরি থেকে নেয়া অ্যালগরিদম ব্যবহার করে তৈরি আরএসএ কিগুলোকে আক্রান্ত করে। স্মার্ট কার্ড এবং টিপিএমের বড় সংখ্যা এতে আক্রান্ত হয়। ঐ দলের দ্বারা প্রকাশিত প্রোগ্রাম ব্যবহার করে দুর্বল আরএসএ কিগুলোকে সহজেই বের করা যায়।^[৩৩]

শক্তিশালী সংখ্যা তৈরির গুরুত্ব

মৌলিক সংখ্যা p এবং q তৈরি করার জন্য একটি গুপ্তবিদ্যায় শক্তিশালী সংখ্যা জেনারেটর বা উদ্ভাবক ব্যবহার করতে হবে, যেটিকে সঠিকভাবে গঠন করা হয়েছে। ২০১২সালের শিরুতে আরজেন কে. লেন্স্ট্রা, জেমস পি. হিউজেস, ম্যাক্সিম অগি, জোপ ডাব্লিউ. বোস, থর্স্টেন ক্লেইনজাংগ এবং ক্রিস্টোফে ওয়াচটার ইন্টারনেটের বিভিন্ন পাবলিক কি তুলনা করে একটি গবেষণা প্রকাশ করেন। তারা শুধুমাত্র ইউক্লিডের অ্যালগরিধম ব্যবহার করে কিগুলোর ০.২% ফ্যাক্টর করতে সক্ষম হয়েছিল।^{[৩৪][৩৫]}

তারা পূর্ণসংখ্যার ফ্যাক্টরাইজেশনের উপর ভিত্তি করে গুপ্তবিদ্যার একটি দুর্বলতা বের করেন। যদি n = pq একটি পাবলিক কি এবং n′ = p′q′ আরেকটি পাবলিক কি হয়, তাহলে কোন কারণে p = p′ (কিন্তুbut q, q′ এর সমান নয়), তাহলে একটি ছোট হিসাব gcd(n,n′) = p n এবং n′ উভয়ের ফ্যাক্টর করে, যা উভয় কিকে দুর্বল করে দেয়। লেন্স্ট্রা এট আল. উল্লেখ করেন যে এই সমস্যাটিকে হ্রাস করা যাবে নিরাপত্তা লেভেলের দ্বিগুণ বিট দৈর্ঘ্যের শক্ত সংখ্যা ব্যবহার করে অথবা একটি নির্দিষ্ট ফাংশন ব্যবহার করে যা q এবং p চয়ন করবে, স্বাধীনভাবে p এবং q নেিয়ার পরিবর্তে।

একই ধরনের এক গবেষণার দলের সাথে যুক্ত ছিলেন নাদিয়া হেনিঙ্গার। তারা n (যা তারা পেয়েছিল, একটি ৭২৯মিলিয়ন ডিজিট সংখ্যা) এর গুণফল বের করার বিপরীতে ড্যানিয়েল জে. বার্নস্টেইনের একটি মতবাদকে ব্যবহার করেন প্রত্যেক আরএসএ কি n জিসিডি গণনা করার জন্য, প্রতিটি জিসিডি(n,n′) আলাদাভাবে গণনার পরিবর্তে, এটির দ্বারা আরও দ্রুত কাজ সম্পন্ন করা সম্ভব হয়েছে।

হেনিঙ্গার তার ব্লগে বলেন যে খারাপ কিগুলোর বেশিরভাগ ছিল সংযুক্ত এপ্লিকেশনগুলোতে, যাদের মধ্যে ছিল ৩০টিরও বেশি প্রতিষ্ঠানের "ফায়ারওয়াল, রাউটার, ভিপিএন যন্ত্র, প্রিন্টাট, প্রজেক্টর, রিমোট সার্ভার এডমিনিস্ট্রেশন যন্ত্র এবং ভিওআইপি ফোন"। হেনিঙ্গার বর্ণনা করেন যে দুটি দল দ্বারা উদ্ভূত ওয়ান-শেয়ার্ড-প্রাইম সমস্যাটি হয় মূলত তখন যখন প্রাথমিক অবস্থায় এলোমেলা সংখ্যা জেনারটর বা তেরিকারকে দুর্বল সিড ব্যবহার করা হয় এবং প্রথম ও দ্বিতীয় মৌলিক সংখ্যার সময় পুনরায় এটিতে সিড ব্যবহার করা হয়। উচ্চ এনট্রোপির সিড ব্যবহার করে যা সময়ের কি স্ট্রোক বা বৈদ্যুতিক ডায়োড শব্দ বা দুটি স্টেশনের মাঝে রেডিও গ্রাহকের শব্দ থেকে নেয়া যায়, এই সমস্যাটি সমাধান করতে পারবে।^[৩৬]

পাবলিক কি গুপ্তকরণের প্রতিটি ধাপে শক্ত সংখ্যা তৈরি খুব গুরুত্বপূর্ণ। উদাহরণ স্বরুপ, যদি আরএসএ তে পাঠানো হবে এমন সামঞ্জস্যপূর্ণ কিতে দুর্বল সংখ্যা জেনারেটর বা উৎপাদক ব্যবহার করা হয়, তবে ইভসড্রপার আরএসএকে উপেক্ষা করতে পারবে এবং সামঞ্জস্যপূর্ণ কিগুলোকে সরাসরি অনুমান করতে পারবে।

সময়জ্ঞান আক্রমণ

পল কোচার ১৯৯৫সালে আরএসএর উপর নতুন একটি আক্রমণ ব্যাখ্যা করেন: যদি আক্রমণকারী ইভ এলিসের হার্ডওয়্যার সম্পর্কে যথেষ্ট তথ্য জানে এবং কিছু পরিচিত গুপ্তবার্তার ডিক্রিপশন সময় পরিমাপ করতে সক্ষম হয়, তাহলে সে ডিক্রিপশন কি d দ্রুত অনুমান করতে পারবে। এই আক্রমণটি আরএসএ স্বাক্ষর স্কিমেও করা যায়। ২০০৩সালে, বোনেহ এবং ব্রুমলে এই আক্রমণটি আরও ব্যবহারিকভাবে করে দেখান কীভাবে একটি নেটওয়ার্ক সংযোগ থেকে আরএসএ গুনক পাওয়া যায়। (উদাহরণ স্বরুপ, একটি এসএসএল করা ওয়েবসার্ভার থেকে)^[৩৭] আরএসএ কার্যকরে ব্যবহৃত চীনা ভাজক উপপাদ্য হতে ফাঁস হওয়া তথ্যকে নিয়ে এই আক্রমণে কাজে লাগানো হয়।

এই আক্রমণ থেকে বাঁচার একটি পথ হলো যাতে প্রত্যেকটি গুপ্তবার্তা ডিক্রিপশনে একই সময় লাগে তা নিশ্চিত করা। যদিও, এই প্রচেষ্টা কর্মক্ষমতাকে ব্যাপক হ্রাস করে দিতে পারে। এর পরিবর্তে, আরএসএতে অন্য ধরনের পদ্ধতি ব্যবহার করা হয় যা ব্লাইন্ডিং হিসেবে পরিচিত। আরএসএ ব্লাইন্ডিং মূলত আরএসএ র বর্ধক মানটিকে কাজে লাগায়। c^d (mod n) গণনার পরিবর্তে, এলিস প্রথমে একটি এলোমেলো গোপন মান r নেয় এবং (r^ec)^d (mod n) গণনা করে। ইউলারের উপপাদ্য প্রয়োগ করার পর এই গণনার ফল হবে rc^d (mod n) আর এখান থেকে r এর পরিপূরক দিয়ে গুণ করে r কে বাদ দেয়া যায়। প্রতিটি গুপ্তবার্তার জন্য r এর নতুন মান নেয়া হয়। ব্লাইন্ডিং প্রয়োগ করার পরে, ডিক্রিপশন সময় একটির সাথে অন্যটির কোন সম্পর্ক থাকে না তাই সময়জ্ঞান আক্রমণ ব্যহত হয়।

সাইড-চ্যানেল এনালাইসিস আক্রমণ

এখানে ব্রাঞ্চ প্রেডিকশন এনালাইসিস (বিপিএ) ব্যবহার করে একটি সাইড-চ্যানেল আক্রমণ বর্ণনা করা হয়েছে। অনেক প্রসেসর ব্রাঞ্চ নির্ণায়ক ব্যবহার করে যাতে কোন প্রোগ্রামের নির্দেশনা তালিকায় থাকা শর্তমূলক ব্রাঞ্চকে নিতে হবে কিনা তা জানা যায়। অনেক সময় এই প্রসেসরগুলো সিমুলটেনাস মাল্টিথ্রেডিং (এসএমটি) প্রয়োগ করে। ব্রাঞ্চ প্রেডিকশন এনালাইসিস এই প্রসেসরগুলো দিয়ে একটি স্পাই প্রসেস চালায় প্রাইভেট কি আবিষ্কার করার জন্য।

সিম্পল ব্রাঞ্চ প্রেডিকশন এনালাইসিস (এসবিপিএ) দাবি করে এটি অ-পরিসংখ্যানগতভাবে বিপিএ কে উন্নত করতে পেরেছে। তাদের কাগজে, "সিম্পল ব্রাঞ্চ প্রেডিকশন এনালাইসিসের ক্ষমতায়",^[৩৮] এসবিপিএর উদ্ভাবকরা (ওনার এসিকমেজ এবং সেটিন কায়া কস) দাবি করে আরএসএ কির ১০বার পুনরাবৃত্তিতে তারা ৫১২বিটের মাঝে ৫০৮বিটকে আবিষ্কার করতে পেরেছে।

আরএসএ র কার্যকারীতায় একটি পাওয়ার ত্রুটি আক্রমণ সম্পর্কে ২০১০সালে বর্ণনা করা হয়েছে।^[৩৯] উদ্ভাবক সিপিইউতে ক্ষমতার বাইরে বিভিন্ন মানের ভোল্টেজ দিয়ে কি পেতে সক্ষম হয়েছিল; এটির কারণে সার্ভারে নানা পাওয়ার ত্রুটি দেখা দেয়।

রেইনবো টেবিল আক্রমণ

তৈরি করা মৌলিক সংখ্যাগুলোকে রেইনবো টেবিল দ্বারা আক্রমণ করা যায় কারণ এলোমেলো সংখ্যাগুলো নির্দিষ্ট এবং সসীম।^[৪০]

বাস্তবায়ন

নিচের গুপ্তবিদ্যার ভান্ডারগুলো আরএসএ-র জন্য সহযোগীতা প্রদান করে থাকে:

• বোটান
• বাউন্সি ক্যাসেল
• ক্রিপ্টলিব
• ক্রিপ্টো++
• লিবজিক্রিপ্ট
• নেটল
• ওপপনএসএসএল
• উল্ফক্রিপ্ট

তথ্যসূত্র

1. Smart, Nigel (ফেব্রুয়ারি ১৯, ২০০৮)। "Dr Clifford Cocks CB"। Bristol University। সংগ্রহের তারিখ আগস্ট ১৪, ২০১১। 
2. Rivest, R.; Shamir, A.; Adleman, L. (ফেব্রুয়ারি ১৯৭৮)। "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" (পিডিএফ)। Communications of the ACM। 21 (2): 120–126। ডিওআই:10.1145/359340.359342। সাইট সিয়ারX 10.1.1.607.2677 । ১৭ ডিসেম্বর ২০০৮ তারিখে মূল (পিডিএফ) থেকে আর্কাইভ করা। সংগ্রহের তারিখ ১৭ আগস্ট ২০১৯। 
3. Diffie, W.; Hellman, M.E. (নভেম্বর ১৯৭৬)। "New directions in cryptography"। IEEE Transactions on Information Theory। 22 (6): 644–654। আইএসএসএন 0018-9448। ডিওআই:10.1109/TIT.1976.1055638। সাইট সিয়ারX 10.1.1.37.9720 । 
4. Rivest, Ronald। "The Early Days of RSA -- History and Lessons" (পিডিএফ)। 
5. Calderbank, Michael (২০০৭-০৮-২০)। "The RSA Cryptosystem: History, Algorithm, Primes" (পিডিএফ)। 
6. Robinson, Sara (জুন ২০০৩)। "Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders" (পিডিএফ)। SIAM News। 36 (5)। ১৬ জানুয়ারি ২০১৭ তারিখে মূল (পিডিএফ) থেকে আর্কাইভ করা। সংগ্রহের তারিখ ১৭ আগস্ট ২০১৯। 
7. Cocks, C.C. (২০ নভেম্বর ১৯৭৩)। "A Note on Non-Secret Encryption" (পিডিএফ)। www.gchq.gov.uk। ১৬ ফেব্রুয়ারি ২০১৭ তারিখে মূল (পিডিএফ) থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২০১৭-০৫-৩০। 
8. Jim Sauerberg "From Private to Public Key Ciphers in Three Easy Steps" ওয়েব্যাক মেশিনে আর্কাইভকৃত ৯ মে ২০১৭ তারিখে.
9. Margaret Cozzens and Steven J. Miller. "The Mathematics of Encryption: An Elementary Introduction". p. 180.
10. Alasdair McAndrew. "Introduction to Cryptography with Open-Source Software". p. 12.
11. Surender R. Chiluka. "Public key Cryptography".
12. Neal Koblitz. "Cryptography As a Teaching Tool". Cryptologia, Vol. 21, No. 4 (1997).
13. "RSA Security Releases RSA Encryption Algorithm into Public Domain"। জুন ২১, ২০০৭ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২০১০-০৩-০৩। 
14. Boneh, Dan (১৯৯৯)। "Twenty Years of attacks on the RSA Cryptosystem"। Notices of the American Mathematical Society। 46 (2): 203–213। 
15. Applied Cryptography, John Wiley & Sons, New York, 1996. Bruce Schneier, p.467
16. McKee, James; Pinch, Richard (১৯৯৮)। "Further Attacks on Server-Aided RSA Cryptosystems"। সাইট সিয়ারX 10.1.1.33.1333 । 
17. A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, Springer-Verlag, New York, 1987. Neal Koblitz, Second edition, 1994. p. 94
18. Dukhovni, Viktor (জুলাই ৩১, ২০১৫)। "common factors in (p − 1) and (q − 1)"। openssl-dev (মেইলিং তালিকা)। জুন ৮, ২০১৯ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ সেপ্টেম্বর ১, ২০১৯। উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link)
19. Dukhovni, Viktor (আগস্ট ১, ২০১৫)। "common factors in (p − 1) and (q − 1)"। openssl-dev (মেইলিং তালিকা)। জুন ৮, ২০১৯ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ সেপ্টেম্বর ১, ২০১৯। উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link)
20. Johnson, J.; Kaliski, B. (February 2003). Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1. Network Working Group. RFC 3447. http://tools.ietf.org/html/rfc3447। সংগৃহীত হয়েছে 9 March 2016.
21. Scholz, Florian; Shepherd, Eric। "Math.random()"। Mozilla Developer Network। সংগ্রহের তারিখ ৫ জুন ২০১৬। 
22. Håstad, Johan (১৯৮৬)। "On using RSA with Low Exponent in a Public Key Network"। Advances in Cryptology — CRYPTO '85 Proceedings। Lecture Notes in Computer Science। 218। পৃষ্ঠা 403–408। আইএসবিএন 978-3-540-16463-0। ডিওআই:10.1007/3-540-39799-X_29। 
23. Coppersmith, Don (১৯৯৭)। "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities" (পিডিএফ)। Journal of Cryptology। 10 (4): 233–260। ডিওআই:10.1007/s001459900030। সাইট সিয়ারX 10.1.1.298.4806 । 
24. S. Goldwasser and S. Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Annual ACM Symposium on Theory of Computing, 1982.
25. "RSA Algorithm"। 
26. Machie, Edmond K.। Network security traceback attack and react in the United States Department of Defense network। পৃষ্ঠা 167। আইএসবিএন 1466985747। 
27. "Yafu"। 
28. "Solo Desktop Factorization of an RSA-512 Key"। ২০০৯-০৮-২৫। 
29. Miller, Gary L. (১৯৭৫)। "Riemann's Hypothesis and Tests for Primality" (পিডিএফ)। Proceedings of Seventh Annual ACM Symposium on Theory of Computing। পৃষ্ঠা 234–239। উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link)
30. Sandee, Michael (নভেম্বর ২১, ২০১১)। "RSA-512 certificates abused in-the-wild"। Fox-IT International blog। 
31. Silverman, Robert D. (এপ্রিল ৮, ২০০২)। "Has the RSA algorithm been compromised as a result of Bernstein's Paper?"। sec. "What key size should I be using?"। ২০১৩-০৯-২৩ তারিখে মূল থেকে আর্কাইভ করা। 
32. Wiener, Michael J. (মে ১৯৯০)। "Cryptanalysis of short RSA secret exponents" (পিডিএফ)। IEEE Transactions on Information Theory। 36 (3): 553–558। ডিওআই:10.1109/18.54902। 
33. Nemec, Matus; Sys, Marek; Svenda, Petr; Klinec, Dusan; Matyas, Vashek (নভেম্বর ২০১৭)। "The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli" (পিডিএফ)। Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security। CCS '17। ডিওআই:10.1145/3133956.3133969। উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link)
34. Markoff, John (ফেব্রুয়ারি ১৪, ২০১২)। "Flaw Found in an Online Encryption Method"। The New York Times। 
35. Lenstra, Arjen K.; Hughes, James P.; Augier, Maxime; Bos, Joppe W.; Kleinjung, Thorsten; Wachter, Christophe (২০১২)। "Ron was wrong, Whit is right" (পিডিএফ)। 
36. Heninger, Nadia (ফেব্রুয়ারি ১৫, ২০১২)। "New research: There's no need to panic over factorable keys–just mind your Ps and Qs"। Freedom to Tinker। 
37. Brumley, David; Boneh, Dan (২০০৩)। "Remote timing attacks are practical" (পিডিএফ)। Proceedings of the 12th Conference on USENIX Security Symposium। SSYM'03। উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link)
38. Acıiçmez, Onur; Koç, Çetin Kaya; Seifert, Jean-Pierre (২০০৭)। "On the power of simple branch prediction analysis"। Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security। ASIACCS '07। পৃষ্ঠা 312–320। ডিওআই:10.1145/1229285.1266999। সাইট সিয়ারX 10.1.1.80.1438 । উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link)
39. Pellegrini, Andrea; Bertacco, Valeria; Austin, Todd (২০১০)। "Fault-Based Attack of RSA Authentication" (পিডিএফ)। 
40. 现实RSA算法的破解