Cryptography Challenges – CTF Writeup
এই লেখায় তিনটি Cryptography challenge-এর ধারণা, দুর্বলতা এবং সমাধানের পদ্ধতি আলোচনা করা হয়েছে। প্রতিটি challenge-এ ব্যবহৃত cryptographic concept বুঝে নেওয়া এবং challenge-এর দেওয়া data দিয়ে ফলাফল যাচাই করা গুরুত্বপূর্ণ।
01. Secret Keeper
Challenge Overview
এই challenge-এ secret_keeper.py নামের একটি Python script দেওয়া হয়েছিল। Script-টি XOR operation ব্যবহার করে plaintext encrypt করত। আমাদের কাছে plaintext এবং Base64 encoded ciphertext দেওয়া ছিল, কিন্তু secret key লুকানো ছিল।
Challenge Code
def byte_xor(ba1, ba2):
return bytes([
_a ^ _b
for _a, _b in zip(ba1, ba2)
])
# The "Lost" Key
key = "???????????????????????????????????????????"
# Known plaintext
plaintext = "The XOR cipher is a simple encryption technique that combines plaintext with a key using the exclusive OR operation"
# Base64 encoded ciphertext
ciphertext_b64 = "DgEmSDkiIlsbWQI3DhwQHh1/EUxHWAMEXx1UOloXBk0TH0gS"
Understanding the Vulnerability
XOR-এর একটি গুরুত্বপূর্ণ বৈশিষ্ট্য হলো একই value দিয়ে দুবার XOR করলে আগের value ফিরে পাওয়া যায়।
A XOR B = C
C XOR A = B
Therefore:
Key = Plaintext XOR Ciphertext
plaintext এবং ciphertext দুটোই জানা থাকলে key পুনরুদ্ধার করা সম্ভব। এই ধরনের আক্রমণকে Known Plaintext Attack বলা হয়।
Solution
import base64
ciphertext_b64 = "DgEmSDkiIlsbWQI3DhwQHh1/EUxHWAMEXx1UOloXBk0TH0gS"
plaintext = (
"The XOR cipher is a simple encryption technique "
"that combines plaintext with a key using the "
"exclusive OR operation"
)
ciphertext = base64.b64decode(ciphertext_b64)
key = bytes(
c ^ p
for c, p in zip(ciphertext, plaintext.encode())
)
print(key.decode())
ZiChamp{x0r_kn0wn_pl41nt3xt_4tt4ck!}02. Text Mixer
Challenge Overview
এই challenge-এ একটি Transposition Cipher ব্যবহার করা হয়েছিল। Character-এর মান পরিবর্তন না করে secret permutation দিয়ে তাদের অবস্থান পরিবর্তন করা হয়েছিল।
Challenge Code: textmixer.py
import random
# Generate a random permutation (this stays secret!)
PERM = list(range(16))
random.shuffle(PERM)
def mix_text(text):
"""Apply our secret permutation to mix up 16-character text."""
assert len(text) == 16, "Text must be exactly 16 characters!"
return ''.join(text[PERM[i]] for i in range(16))
if __name__ == "__main__":
# Let's demonstrate with some test patterns and the secret flag!
inputs = [
"aaaabbbbccccdddd",
"abcdabcdabcdabcd",
open("flag.txt").read().strip()
]
for text in inputs:
mixed = mix_text(text)
print(f"{text} -> {mixed}")
Understanding the Vulnerability
একই permutation একই script চলাকালে সব input-এর জন্য ব্যবহার করা হয়েছিল। দুটি পরিচিত input-output pair বিশ্লেষণ করে permutation পুনরুদ্ধার করা যায়।
Input 1:
aaaabbbbccccdddd
Output 1:
aabcdacdbdcbdacb
Input 2:
abcdabcdabcdabcd
Output 2:
cdbbdbabdacacadc
Recovering the Permutation
প্রথম input-এ a রয়েছে index 0, 1, 2, 3-এ। দ্বিতীয় input-এ c রয়েছে index 2, 6, 10, 14-এ। প্রথম output character দুটো pattern-এ যথাক্রমে a ও c, তাই intersection থেকে index 2 পাওয়া যায়। একইভাবে প্রতিটি position বের করা যায়।
in1 = "aaaabbbbccccdddd"
out1 = "aabcdacdbdcbdacb"
in2 = "abcdabcdabcdabcd"
out2 = "cdbbdbabdacacadc"
perm = [0] * 16
for i in range(16):
candidates1 = {
idx for idx, char in enumerate(in1)
if char == out1[i]
}
candidates2 = {
idx for idx, char in enumerate(in2)
if char == out2[i]
}
common = candidates1 & candidates2
if len(common) != 1:
raise ValueError("Permutation is ambiguous")
perm[i] = common.pop()
print("Recovered permutation:", perm)
Decrypting the Flag
Permutation পাওয়া গেলে output-এর প্রতিটি character-কে তার original index-এ ফিরিয়ে দিতে হবে। নিচের অংশে challenge-এর scrambled flag বসাতে হবে।
mixed_flag = "PUT_THE_16_CHARACTER_OUTPUT_HERE"
flag_list = [''] * 16
for i in range(16):
flag_list[perm[i]] = mixed_flag[i]
flag = ''.join(flag_list)
print(flag)
ZiChamp{y0u_cr4ck3d_1t!!}3. PrimeTime – RSA Factorization Attack
The Challenge
এই Challenge-এ আমাদের একটি standard RSA public key এবং একটি encrypted message দেওয়া হয়েছিল। Public key-এর মধ্যে ছিল n এবং e। পাশাপাশি intercepted.txt নামের একটি আলাদা ফাইলে পাওয়া যায় RSA modulus-এর একটি leaked prime factor q।
আমাদের লক্ষ্য ছিল এই তথ্য ব্যবহার করে RSA private key পুনরুদ্ধার করা এবং encrypted message decrypt করে আসল flag বের করা।
The Vulnerability
RSA encryption-এর নিরাপত্তা নির্ভর করে একটি বড় সংখ্যাকে দুটি prime factor-এ ভাগ করার কঠিন সমস্যার ওপর। RSA modulus তৈরি হয় দুটি বড় prime number গুণ করে:
N = p × q
সাধারণ অবস্থায় শুধু N জানা থাকলে p এবং q বের করা computationally কঠিন। কিন্তু এই Challenge-এ q আগেই leak হয়ে গিয়েছিল। ফলে পুরো RSA key ভেঙে ফেলা অনেক সহজ হয়ে যায়।
Step 1: Recover the Prime Factor
যেহেতু আমাদের কাছে N এবং q দুটিই রয়েছে, তাই খুব সহজেই division করে অন্য prime factor p বের করা সম্ভব:
p = N // q
এখানে // ব্যবহার করা হয়েছে integer division-এর জন্য। এরপর যাচাই করা হয় যে p এবং q উভয়ই prime number কি না।
Step 2: Calculate the Private Key
এখন আমাদের কাছে RSA-এর দুটি prime factor রয়েছে। এগুলো ব্যবহার করে Euler's Totient Function হিসাব করা যায়:
φ(N) = (p − 1) × (q − 1)
এরপর public exponent e-এর modular multiplicative inverse বের করে private exponent d নির্ণয় করতে হবে:
d = e⁻¹ mod φ(N)
Python-এ pow(e, -1, phi) ব্যবহার করে সহজেই এই হিসাব করা যায়।
Step 3: Decrypt the Message
Private exponent d পাওয়া গেলে RSA decryption formula ব্যবহার করে original message পুনরুদ্ধার করা সম্ভব:
m = cᵈ mod N
এখানে c হলো encrypted ciphertext এবং m হলো decrypted message। শেষে long_to_bytes() ব্যবহার করে সংখ্যাটিকে আবার readable bytes-এ রূপান্তর করা হয়।
Python Solution
নিচের Python script-টি challenge-এর দেওয়া values ব্যবহার করে সম্পূর্ণ process সম্পন্ন করে। প্রথমে leaked factor যাচাই করে, তারপর private key তৈরি করে এবং সবশেষে ciphertext decrypt করে।
from Crypto.Util.number import long_to_bytes, isPrime
# 1. Load the exact values from the challenge files
n = 27176393407935103481163155837427742913736162805163960331439171299917803847839120808804732675657161001205777890520029973936343262372935454665420601809184894777707812681056603978295816651555470815138953238837510805670059628515533201723738377384999931828902088379359668739224568459312311491647662096047608516941790769030123418245983210222253698355788103344141929121912734282726220821892263490249842323331218356969957620712358194016204473618770451542777841273366511873769514760320835637280801421908082271238575146984814792169032375163458775970856228129500375398873773737464366440067238916256182804432304462869247002029101
e = 65537
q_leaked = 168008506905664925715285139876758539830754830224705503363675220828724350021417486524153965414795915910336943871042520716787575587167438973647616275446906752249150745789966942951708080250022889744527067101811169627378390925138067431522589236137308344943601351833634383376801541020263961063873667195177625444329
c = 7542069583043416807452553211097827563470682071572429815679869990681195991689118606379814159564977708578317869931634576286998617751467377481689531028872559287315494504937856065012239953916794992144403922067468433860167270142361449581924727575288593745784169996502257109659927206432888579117792656968701076957165772580318947902569670302444363484622324132788629212183317805804668382990889253975525432562896059378168492513786491326868679194138009976194283715088628524705176665804404751533851985305547948231110262797494804504609270604282807272038498673992761913057381230614846843958234511763979488427254180506475264982385
# 2. Key Recovery Logic
print("[-] Checking factors...")
if n % q_leaked == 0:
p = n // q_leaked
# Verify both factors are prime
if isPrime(p) and isPrime(q_leaked):
print("[+] Standard RSA confirmed (n = p * q)")
# Calculate private exponent d
phi = (p - 1) * (q_leaked - 1)
d = pow(e, -1, phi)
# Decrypt the ciphertext
m = pow(c, d, n)
flag_raw = long_to_bytes(m)
print(f"\n[+] DECRYPTED TEXT: {flag_raw.decode()}")
else:
print("[!] Warning: p or q is not prime! This might be Multi-Prime RSA.")
else:
print("[!] Error: q is not a factor of n!")
Alternative Method: Using dCode.fr
Python code লিখে সমাধান করার পাশাপাশি চাইলে dcode.fr ওয়েবসাইট ব্যবহার করেও RSA decryption করা যায়। সেখানে প্রয়োজনীয় RSA parameters দিয়ে হিসাব করা সম্ভব। অর্থাৎ, হাতে করে Python script না লিখেও challenge-টি solve করা যেতে পারে।
তবে এই পদ্ধতিতে সঠিকভাবে N, e, q এবং ciphertext ব্যবহার করতে হবে। Tool-এর দেওয়া output যাচাই করে তারপর flag গ্রহণ করা উচিত।
Conclusion
এই তিনটি challenge দেখিয়েছে যে cryptographic algorithm-এর নাম শক্তিশালী হলেই implementation নিরাপদ হয় না। Leaked information, দুর্বল parameter এবং repeated permutation-এর মতো ভুল security ভেঙে দিতে পারে।
- Secret Keeper: XOR এবং Known Plaintext Attack।
- Text Mixer: Permutation recovery।
- PrimeTime: RSA factor leakage।
Cryptography শেখার সবচেয়ে ভালো উপায় হলো algorithm-এর পেছনের mathematics বোঝা, implementation বিশ্লেষণ করা এবং প্রতিটি ফলাফল যাচাই করা।
Happy Hacking!
