কম্পিউটেবিলিটি ও ক্রিপ্টোগ্রাফি
এই পাঠে যা শিখবেন
- রাইসের থিওরেম কীভাবে ব্যাখ্যা করে অ্যান্টিভাইরাস/স্ট্যাটিক-অ্যানালাইসিস টুল কেন কখনোই ১০০% সম্পূর্ণ হতে পারে না
- ক্রিপ্টোগ্রাফিক হার্ডনেস অ্যাসাম্পশন কী, এবং কেন এটি হল্টিং প্রবলেমের প্রমাণের চেয়ে ভিন্ন প্রকৃতির
- জিরো-নলেজ প্রুফের মূল ধারণা এবং NP-এর সাথে এর সরাসরি সম্পর্ক
- একটি বাস্তব, কোড-ভেরিফায়েড ডেমো — গুণ করা কেন সহজ কিন্তু ফ্যাক্টর করা তুলনামূলক কঠিন
১ · ডিসাইডেবিলিটি থিওরি বাস্তবে — কেন অ্যান্টিভাইরাস কখনো নিখুঁত নয়
M9/L41-এ আমরা রাইসের থিওরেমRice's Theoremএকটি টুরিং মেশিনের ভাষা সম্পর্কে যেকোনো নন-ট্রিভিয়াল সিমান্টিক প্রপার্টি সাধারণভাবে ডিসাইড করা আনডিসাইডেবল।
প্রমাণ করেছিলাম এবং একটি উদাহরণ হিসেবে "একটি প্রোগ্রাম ভাইরাস কি না" প্রশ্নটি ব্যবহার করেছিলাম। এই পাঠে সেই ফলাফলটিকে
সরাসরি বাস্তব সফটওয়্যার সিকিউরিটির সাথে যুক্ত করছি (cross-ref ../cybersecurity/)। "এই প্রোগ্রামটি কি
ম্যালওয়্যার?" — এটি প্রোগ্রামের একটি নন-ট্রিভিয়াল সিমান্টিক প্রপার্টি, তাই রাইসের থিওরেম অনুযায়ী এটি সাধারণভাবে
আনডিসাইডেবল — কোনো অ্যালগরিদম কখনোই সব সম্ভাব্য প্রোগ্রামের জন্য এই প্রশ্নের ১০০% সঠিক উত্তর দিতে
পারবে না। এই কারণেই বাস্তব অ্যান্টিভাইরাস সফটওয়্যার সিগনেচার-ম্যাচিং ও হেউরিস্টিক ব্যবহার করে — একটি সাধারণ,
সবসময়-সঠিক ডিসিশন প্রসিডিওর গাণিতিকভাবেই অসম্ভব, প্রযুক্তির অভাব নয়।
গুরুত্বপূর্ণ পার্থক্য: অ্যান্টিভাইরাস অসম্পূর্ণ কারণ প্রযুক্তি এখনো যথেষ্ট উন্নত নয় — তা নয়। এটি অসম্পূর্ণ কারণ M9/L41-এর প্রমাণ দেখায় সমস্যাটি নিজেই ফরমালি আনডিসাইডেবল। কোনো ভবিষ্যতের অ্যালগরিদম, কোনো পরিমাণ কম্পিউটিং পাওয়ার দিয়েও এই সীমাবদ্ধতা অতিক্রম করা সম্ভব নয়।
২ · ক্রিপ্টোগ্রাফিক হার্ডনেস অ্যাসাম্পশন
কম্পিউটেবিলিটি থিওরি বলে "সমাধানযোগ্য বনাম সমাধানের অযোগ্য"; কমপ্লেক্সিটি থিওরি (M10-M11) বলে "সমাধানযোগ্য হলে কতটা দ্রুত"। আধুনিক ক্রিপ্টোগ্রাফি এই দ্বিতীয় প্রশ্নের উপর দাঁড়িয়ে আছে — নিরাপত্তা নিশ্চিত করা হয় এমন কিছু গাণিতিক সমস্যা বেছে নিয়ে যেগুলো সমাধানযোগ্য কিন্তু (বর্তমানে জানা অ্যালগরিদম দিয়ে) দ্রুত সমাধানযোগ্য নয়। দুটি সবচেয়ে বিখ্যাত উদাহরণ —
একটি বড় সংখ্যা $n = p \times q$ (দুটি বড় মৌলিক সংখ্যার গুণফল) দেওয়া থাকলে $p$, $q$ খুঁজে বের করা — RSA ক্রিপ্টোসিস্টেমের ভিত্তি।
$g^x \equiv y \pmod{p}$ সমীকরণে $y, g, p$ জানা থাকলে $x$ খুঁজে বের করা — Diffie-Hellman ও অনেক আধুনিক ক্রিপ্টোসিস্টেমের ভিত্তি।
উভয় সমস্যার জন্যই বর্তমানে জানা সেরা ক্লাসিক্যাল অ্যালগরিদম ইনপুটের বিট-সাইজের সাপেক্ষে সুপারপলিনমিয়াল সময় নেয় — অর্থাৎ, $n$-এর মান নয়, বরং $n$ লিখতে কত বিট লাগে (প্রায় $\log_2 n$) তার সাপেক্ষে হার্ড। এই নির্দিষ্ট পার্থক্যটি গুরুত্বপূর্ণ, নিচের কোড সেলে সরাসরি দেখা যাবে।
M9/L39-এর হল্টিং প্রবলেমের আনডিসাইডেবিলিটি একটি ফরমালি প্রমাণিত ফলাফল — কোনো সন্দেহ নেই। কিন্তু "ফ্যাক্টরিং হার্ড" — এটি প্রমাণিত নয়, এটি একটি ব্যাপকভাবে বিশ্বাসযোগ্য অনুমান (widely-believed assumption)। কেউ কখনো প্রমাণ করেনি যে ফ্যাক্টরিং-এর জন্য কোনো দ্রুত (পলিনমিয়াল-টাইম) অ্যালগরিদম থাকতে পারে না — শুধু এখন পর্যন্ত কেউ খুঁজে পায়নি। তাই আধুনিক ক্রিপ্টোগ্রাফির নিরাপত্তা মৌলিকভাবে এমন গাণিতিক ভিত্তির উপর দাঁড়িয়ে আছে যা হল্টিং প্রবলেমের মতো নিশ্চিত নয় — একটি সত্যিকারের গুরুত্বপূর্ণ নুয়ান্স, যা প্রতিটি সিকিউরিটি ইঞ্জিনিয়ারের বোঝা উচিত।
৩ · জিরো-নলেজ প্রুফ — NP-এর একটি চতুর ব্যবহার
M10/L44-এ আমরা দেখেছিলাম NP-এর সংজ্ঞা একটি সার্টিফিকেট ভেরিফিকেশন ধারণার উপর ভিত্তি করে — একটি সমাধান দ্রুত যাচাই করা যায়, যদিও তা দ্রুত খুঁজে বের করা কঠিন হতে পারে। জিরো-নলেজ প্রুফ এই ধারণাকে একটি চতুর, ইন্টারেক্টিভ প্রোটোকলে রূপান্তরিত করে — এক পক্ষ (প্রুভার) অন্য পক্ষকে (ভেরিফায়ার) প্রমাণ করতে পারে যে সে একটি NP সমস্যার (যেমন M10/L47-এর গ্রাফ কালারিং) সমাধান জানে, সমাধানটি আদৌ প্রকাশ না করেই — একাধিকবার র্যান্ডম চ্যালেঞ্জ-রেসপন্স রাউন্ডের মাধ্যমে ভেরিফায়ারকে পরিসংখ্যানগতভাবে নিশ্চিত করে। এটি শুধু একটি তাত্ত্বিক কৌতূহল নয় — আধুনিক প্রাইভেসি-সংরক্ষণকারী ক্রিপ্টোগ্রাফিক সিস্টেমে বাস্তবে ব্যবহৃত হয়।
৪ · কোড দিয়ে হার্ডনেস অ্যাসিমেট্রি দেখা
নিচের কোড সেলে multiply(p, q) (গ্রেড-স্কুল গুণ, ডিজিট-বাই-ডিজিট) বনাম factor_naive(n)
(ট্রায়াল ডিভিশন) এর মধ্যে ধাপ-গণনার (step-count) পার্থক্য দেখানো হয়েছে — real wall-clock টাইমিং নয়, বরং একটি
ডিটারমিনিস্টিক, হার্ডওয়্যার-নিরপেক্ষ প্রক্সি, যাতে ফলাফল প্রতিবার একই থাকে। সতর্কতা: এটি শুধুই
একটি ইলাস্ট্রেটিভ ডেমো — কোনোভাবেই ক্রিপ্টোগ্রাফিকভাবে নিরাপদ নয়; বাস্তব ক্রিপ্টোগ্রাফিক প্যারামিটার কয়েকশো বা
কয়েক হাজার বিটের সংখ্যা ব্যবহার করে, যেখানে এই অসামঞ্জস্য আরও বহুগুণ প্রকট হয়ে ওঠে।
# হার্ডনেস অ্যাসিমেট্রি -- multiply() (সহজ) বনাম factor_naive() (তুলনামূলক কঠিন)
# CAUTION: এটি একটি ইলাস্ট্রেটিভ ডেমো মাত্র -- বাস্তব ক্রিপ্টোগ্রাফিক নিরাপত্তা নয়!
# ধাপ-গণনা প্রক্সি ব্যবহার করা হয়েছে (real wall-clock টাইমিং নয়) -- হার্ডওয়্যার-নিরপেক্ষ, ডিটারমিনিস্টিক
def multiply(p, q):
# গ্রেড-স্কুল long multiplication -- প্রতিটি digit x digit multiplication = এক "ধাপ"
p_digits = [int(d) for d in str(p)]
q_digits = [int(d) for d in str(q)]
steps = 0
for qd in q_digits:
for pd in p_digits:
steps += 1
return p * q, steps
def factor_naive(n):
# ট্রায়াল ডিভিশন -- 2 থেকে sqrt(n) পর্যন্ত প্রতিটি সম্ভাব্য ভাজক পরীক্ষা করা
# মান n-এর সাপেক্ষে পলিনমিয়াল, কিন্তু n-এর বিট-দৈর্ঘ্যের (ইনপুট সাইজ) সাপেক্ষে এক্সপোনেনশিয়াল-ঘেঁষা
steps = 0
d = 2
while d * d <= n:
steps += 1
if n % d == 0:
return d, n // d, steps
d += 1
return None, None, steps # n মৌলিক (বা 1)
semiprimes = [(101, 103), (997, 1009), (7919, 7927), (99991, 99989)]
print(f"{'p':>8} {'q':>8} {'n=p*q':>12} | multiply-ধাপ | factor-ধাপ | অনুপাত")
print("-" * 66)
for p, q in semiprimes:
n, mul_steps = multiply(p, q)
f1, f2, fac_steps = factor_naive(n)
assert {f1, f2} == {p, q}, f"ফ্যাক্টরিং ভুল: {n}"
ratio = fac_steps / mul_steps
print(f"{p:>8} {q:>8} {n:>12} | {mul_steps:>12} | {fac_steps:>10} | {ratio:>7.1f}x")multiply-এর ধাপসংখ্যা বাড়ে ডিজিট-সংখ্যার সাথে রৈখিকভাবে (২টি ৫-ডিজিট
সংখ্যার জন্য মাত্র ~২৫ ধাপ), কিন্তু factor_naive-এর ধাপসংখ্যা বাড়ে মানের সাথে (প্রায়
$\sqrt{n}$) — যেহেতু $n$-এর ডিজিট-সংখ্যা সামান্য বাড়লে $n$ নিজেই বহুগুণ বেড়ে যায়, ফ্যাক্টরিং-এর কাজের
পরিমাণ ইনপুট-সাইজের (বিট-সংখ্যার) সাপেক্ষে বহুগুণ দ্রুত বাড়ে — এই অসামঞ্জস্যই বাস্তব ক্রিপ্টোগ্রাফিক হার্ডনেসের মূল
অন্তর্দৃষ্টি, যদিও এখানে ব্যবহৃত সংখ্যাগুলো বাস্তব ব্যবহারের তুলনায় বিলিয়ন গুণ ছোট।
কম্পিউটেবিলিটি থিওরি ও কমপ্লেক্সিটি থিওরি — দুটোই সিকিউরিটি ইঞ্জিনিয়ারিং-এর গভীরে জড়িত। রাইসের থিওরেম ব্যাখ্যা করে কেন স্ট্যাটিক-অ্যানালাইসিস/ম্যালওয়্যার-ডিটেকশন কখনো নিখুঁত হতে পারে না, আর কমপ্লেক্সিটি-হার্ডনেস অ্যাসাম্পশন ব্যাখ্যা করে ক্রিপ্টোগ্রাফি কেন আদৌ কাজ করে — যদিও, সততার সাথে বলতে হয়, সেই ভিত্তি একটি প্রমাণ নয়, একটি বহু-পরীক্ষিত কিন্তু চিরকালের জন্য অপ্রমাণিত অনুমান।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ "অ্যান্টিভাইরাস সফটওয়্যার আরও ভালো ইঞ্জিনিয়ারিং দিয়ে একদিন ১০০% নিখুঁত হয়ে যাবে" — এই দাবিটি কেন ভুল?
কারণ "এই প্রোগ্রামটি ম্যালওয়্যার কি না" প্রশ্নটি প্রোগ্রামের একটি নন-ট্রিভিয়াল সিমান্টিক প্রপার্টি, এবং রাইসের থিওরেম (M9/L41) প্রমাণ করে এমন যেকোনো প্রপার্টি সাধারণভাবে আনডিসাইডেবল — কোনো অ্যালগরিদম সব সম্ভাব্য প্রোগ্রামের জন্য সঠিক উত্তর দিতে পারে না। এটি একটি গাণিতিকভাবে প্রমাণিত সীমাবদ্ধতা, ইঞ্জিনিয়ারিং-এর ঘাটতি নয় — তাই "আরও ভালো ইঞ্জিনিয়ারিং" এটি অতিক্রম করতে পারবে না, শুধু হেউরিস্টিক আরও ভালো করতে পারবে।
প্র ০২ হল্টিং প্রবলেমের আনডিসাইডেবিলিটি এবং "ফ্যাক্টরিং হার্ড" — এই দুই দাবির মধ্যে জ্ঞানতাত্ত্বিক (epistemological) পার্থক্য কী?
হল্টিং প্রবলেমের আনডিসাইডেবিলিটি একটি সম্পূর্ণ, ফরমাল গাণিতিক প্রমাণ (ডায়াগোনালাইজেশন, M9/L39) — কোনো ব্যতিক্রম নেই। কিন্তু "ফ্যাক্টরিং-এর কোনো পলিনমিয়াল-টাইম অ্যালগরিদম নেই" — এটি কখনো প্রমাণিত হয়নি; শুধু কয়েক দশকের নিবিড় গবেষণায় কেউ খুঁজে পায়নি। ভবিষ্যতে কেউ একটি দ্রুত অ্যালগরিদম (বা কোয়ান্টাম কম্পিউটার, যা আসলে Shor's algorithm-এর মাধ্যমে ইতিমধ্যে তাত্ত্বিকভাবে সম্ভব দেখানো হয়েছে) আবিষ্কার করলে পুরো অনুমানটি ভেঙে পড়তে পারে — এটি ঠিক এই কারণেই ঘটে যে RSA-এর মতো সিস্টেম কোয়ান্টাম-প্রতিরোধী ক্রিপ্টোগ্রাফির দিকে ধাবিত হচ্ছে।
প্র ০৩ কোড সেলের সংখ্যাগুলো (৫-ডিজিট সেমিপ্রাইম) দিয়েই ফ্যাক্টরিং "হার্ড" প্রমাণিত হয় কি?
না, একদমই না — এখানে সবচেয়ে বড় ফ্যাক্টরিং-এ মাত্র প্রায় ১,০০,০০০ ধাপ লেগেছে, যা যেকোনো কম্পিউটারে মুহূর্তের মধ্যে সম্পন্ন হয়। বাস্তব RSA এনক্রিপশন ২০৪৮ বা ৪০৯৬-বিট সংখ্যা ব্যবহার করে — সেখানে ট্রায়াল ডিভিশনের ধাপসংখ্যা এত বিশাল যে মহাবিশ্বের বয়সের চেয়েও বেশি সময় লাগবে। এই কোড সেল শুধু দিক ও প্যাটার্ন দেখানোর জন্য (গুণ রৈখিক, ফ্যাক্টরিং দ্রুততর বৃদ্ধি পায়) — বাস্তব নিরাপত্তার মাত্রা প্রমাণ করার জন্য নয়।
অনুশীলন
-
চিন্তা করুন: "যদি কেউ প্রমাণ করে P = NP (M11/L49), তাহলে কি ফ্যাক্টরিং সহজ হয়ে যাবে, এবং তার ফলে RSA ভেঙে পড়বে?" — আপনার যুক্তি লিখুন।
এটি সরাসরি নিশ্চিত নয়, কিন্তু ব্যাপকভাবে বিশ্বাস করা হয় হ্যাঁ, সম্ভবত। ফ্যাক্টরিং NP-তে আছে (একটি ফ্যাক্টর দ্রুত ভেরিফাই করা যায়) কিন্তু এখনো জানা যায়নি এটি NP-কমপ্লিট কি না। তবে যদি P = NP প্রমাণিত হয়, তাহলে NP-এর প্রতিটি সমস্যার (ফ্যাক্টরিং সহ, যেহেতু এটি NP-তে আছে) জন্য একটি পলিনমিয়াল-টাইম অ্যালগরিদম থাকতে হবে (M11/L49-এর সংজ্ঞা অনুযায়ী) — যার অর্থ ফ্যাক্টরিং সহজ হয়ে যাবে এবং RSA-এর নিরাপত্তার ভিত্তি ভেঙে পড়বে। এটিই একটি বড় কারণ কেন P vs NP প্রশ্নটি শুধু তাত্ত্বিক কৌতূহল নয়, বাস্তব ক্রিপ্টোগ্রাফিক গুরুত্বও বহন করে।
-
পরীক্ষা করুন: উপরের কোড সেলে
semiprimesতালিকায় একটি বড় সেমিপ্রাইম যোগ করুন (যেমন(999983, 999979)) এবং Run চেপে দেখুন অনুপাত (ratio) কীভাবে বৃদ্ধি পায়।সংখ্যা যত বড় হবে,
factor_naive-এর ধাপসংখ্যা তত দ্রুত বাড়বে (প্রায় $\sqrt{n}$ হারে) কিন্তুmultiply-এর ধাপসংখ্যা প্রায় একই থাকবে (ডিজিট-সংখ্যা সামান্য বাড়ায়) — ফলে অনুপাত (ratio) প্রতিটি নতুন, বড় উদাহরণে আরও বড় হবে, ঠিক যেমন উপরের টেবিলে ১০১×১০৩ থেকে ৯৯৯৯১×৯৯৯৮৯ পর্যন্ত ~১১x থেকে ~৪০০০x পর্যন্ত অনুপাত বৃদ্ধি পেয়েছিল দেখা গিয়েছিল।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পরবর্তী পাঠ: কমপ্লেক্সিটি থিওরি ও অ্যালগরিদম ডিজাইন পাঠ ৫৩ কমপ্লেক্সিটি থিওরি কীভাবে প্রতিদিনের অ্যালগরিদম-ডিজাইন সিদ্ধান্তে (DP বনাম greedy) সাহায্য করে।
- পুনরালোচনা: রাইসের থিওরেম পাঠ ৪১ রাইসের থিওরেমের সম্পূর্ণ প্রমাণ, যা এই পাঠের ম্যালওয়্যার-ডিটেকশন আলোচনার ভিত্তি।
- Cybersecurity কোর্স সঙ্গী কোর্স ক্রিপ্টোগ্রাফি ও ম্যালওয়্যার-ডিটেকশনের ব্যবহারিক দিক এই কোর্সে বিস্তারিত কভার করা হয়েছে।
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৫৬টি পাঠ DFA/NFA থেকে টুরিং মেশিন, ডিসাইডেবিলিটি ও P বনাম NP পর্যন্ত সম্পূর্ণ কোর্স।