8.7 קריפטו ו RSA פתרון
פתרון - קריפטו ו-RSA¶
כאן נעבור על הפתרון המלא של כל התרגילים, עם המתמטיקה, הקוד והפלט הצפוי. אם עדיין לא ניסיתם לבד - חזרו לתרגול קודם. כל הקוד רץ מקומית מול הקבצים שבניתם בתרגול.
פתרון תרגיל 1 - היפוך ה-cipher¶
הפונקציה encode מבצעת על כל בית שני שלבים לפי הסדר:
כדי לחלץ את in[i] מתוך out[i], מפעילים את ההופכי של כל שלב, בסדר הפוך. הפעולה ההופכית ל-xor היא xor שוב ((t ^ k) ^ k = t), וההופכית לחיבור היא חיסור:
מכיוון שהבינארי עובד בחשבון של unsigned char, כלומר מודולו 256, נשמור על אותו כלל עם & 0xff. נריץ על מערך ה-cipher:
cipher = bytes([0x7a,0x4d,0x62,0x01,0x50,0x40,0x0e,0x4c,
0x6f,0x0a,0x4a,0x49,0xb4,0x0a,0xb7,0x44])
plain = bytes(((c ^ 0x37) - i) & 0xff for i, c in enumerate(cipher))
print(plain) # b'MyS3cr3tP4ssw0rd'
הסיסמה שהתקבלה היא MyS3cr3tP4ssw0rd. נאמת שהיא באמת עוברת את הבדיקה על ידי הפעלת ה-encode קדימה, ואז נזרים אותה לבינארי:
enc = bytes(((plain[i] + i) ^ 0x37) & 0xff for i in range(16))
assert enc == cipher # the solution's encryption equals cipher exactly
הזרמה לבינארי דרך pwntools, שמטפל בבתים הלא מודפסים בלי לפגוע בהם:
from pwn import *
io = process('./cipher_demo')
io.send(plain) # 16 input bytes
print(io.recvall().decode(errors='replace')) # flag content
או ישירות מהמעטפת:
python3 -c "import sys; sys.stdout.buffer.write(bytes(((c^0x37)-i)&0xff for i,c in enumerate(bytes([0x7a,0x4d,0x62,0x01,0x50,0x40,0x0e,0x4c,0x6f,0x0a,0x4a,0x49,0xb4,0x0a,0xb7,0x44]))))" | ./cipher_demo
הפלט הוא תוכן הקובץ flag. אצל האתגר crypto1 האמיתי יש בדרך כלל עוד שכבת קידוד hex לפני הטרנספורמציה, אז שם תוסיפו bytes.fromhex בכניסה ו-.hex() ביציאה - אבל שלד ההיפוך זהה.
למה זה עבד ואיך להכליל: כל שלב בצינור היה הפיך, ו-xor הוא ההופכי של עצמו. הכלל הכללי: מפרקים את הצינור לשלבים, מזהים לכל שלב את הפעולה ההופכית, ומפעילים אותן בסדר הפוך. אם היה ערבוב בין בתים (כל בית תלוי בקודם), היינו מפענחים לפי אותו סדר תלות בדיוק.
פתרון תרגיל 2 - שורש שלישי על RSA¶
נריץ את השירות ונאסוף את הפרמטרים:
הפלט הוא n = ..., e = 3, c = .... המעריך e = 3 הוא הדגל האדום: הצפנה היא c = m^3 mod n. הדגל שלנו קצר - בערך 24 בתים, כלומר m הוא בערך 2^190. לעומת זאת n הוא 2048 ביט, כלומר 2^2048. מכאן m^3 בערך 2^570, הרבה פחות מ-n. לכן לא היה שום צמצום מודולרי, ומתקיים פשוט c = m^3. השורש השלישי השלם של c יחזיר את m:
import gmpy2
from Crypto.Util.number import long_to_bytes
n = ... # from the service's output
e = 3
c = ...
assert e == 3
m, exact = gmpy2.iroot(c, 3)
assert exact, "no exact cube root - m^3 is probably larger than n"
print(long_to_bytes(int(m))) # b'FLAG{demo_rsa_cube_root}'
ואם אין gmpy2, שורש שלישי שלם בחיפוש בינארי:
def icbrt(c):
lo, hi = 0, 1 << ((c.bit_length() // 3) + 2)
while lo < hi:
mid = (lo + hi) // 2
if mid**3 < c:
lo = mid + 1
else:
hi = mid
return lo
m = icbrt(c)
assert m**3 == c
הנה הפתרון המלא כסקריפט pwntools שמתחבר לשירות, מושך את הפרמטרים ומחלץ את הדגל:
from pwn import *
import gmpy2
from Crypto.Util.number import long_to_bytes
io = process(['python3', 'rsa_service.py']) # or remote(host, port)
n = int(io.recvline_startswith(b'n =').split(b'=')[1])
e = int(io.recvline_startswith(b'e =').split(b'=')[1])
c = int(io.recvline_startswith(b'c =').split(b'=')[1])
m, exact = gmpy2.iroot(c, 3)
assert exact
log.success(long_to_bytes(int(m)).decode(errors='replace'))
למה זה עבד ואיך להכליל: המעריך הקטן פוגש מסר קטן, ולכן m^e לא חורג מ-n ואין צמצום. תמיד בדקו את exact: אם הוא False, המסר גדול מ-n^(1/3) והתקפת השורש לא ישימה. אז עוברים ל-Hastad (אם יש כמה מודולוסים) או להתקפה אחרת.
פתרון תרגיל 3 - מודולוס משותף¶
יש לנו c1 = m^e1 mod n ו-c2 = m^e2 mod n עם אותו n ו-gcd(e1, e2) = 1. מכיוון שהמעריכים זרים, אוקלידס המורחב נותן a, b שלמים כך ש-a*e1 + b*e2 = 1. ואז:
חילצנו את m בלי d ובלי פירוק. שימו לב שאחד מ-a, b שלילי, ומעריך שלילי מודולו n פירושו העלאת ההופכי הכפלי בחזקה החיובית - וזה בדיוק מה ש-pow בפייתון 3.8+ עושה לבד:
def egcd(a, b):
if b == 0:
return (a, 1, 0)
g, x, y = egcd(b, a % b)
return (g, y, x - (a // b) * y)
from Crypto.Util.number import long_to_bytes
# n, e1, e2, c1, c2 from the exercise
g, a, b = egcd(e1, e2)
assert g == 1, "the exponents aren't coprime"
m = (pow(c1, a, n) * pow(c2, b, n)) % n
print(long_to_bytes(m)) # b'common modulus is bad'
אם אתם על פייתון ישן שלא תומך במעריך שלילי ב-pow, מטפלים ידנית: הופכים את המקדם השלילי לחיובי ומעלים את ההופכי הכפלי במקומו:
if a < 0:
c1 = pow(c1, -1, n) # the inverse of c1 modulo n
a = -a
if b < 0:
c2 = pow(c2, -1, n)
b = -b
m = (pow(c1, a, n) * pow(c2, b, n)) % n
למה זה עבד ואיך להכליל: התכונה ההומומורפית של RSA לכפל היא זו שאפשרה לשלב את שני הטקסטים המוצפנים למעריך 1. התנאי היחיד הוא gcd(e1, e2) = 1. אם היו יותר משני מעריכים, אפשר לחלץ באותה שיטה מכל זוג שהוא זר.
פתרון תרגיל 4 - שחזור d על ידי פירוק¶
בתרגיל הזה q = nextprime(p + 12345), כלומר p ו-q קרובים מאוד. זה בדיוק המקרה של פירוק Fermat. הרעיון: כותבים n = a^2 - b^2 = (a - b)(a + b). כשהראשוניים קרובים, ה-a המתאים קרוב מאוד ל-sqrt(n), ולכן מוצאים אותו במעט צעדים. מתחילים מ-a = isqrt(n) + 1 ומעלים עד ש-a^2 - n הוא ריבוע מושלם:
from gmpy2 import isqrt
def fermat(n):
a = isqrt(n) + 1
while True:
b2 = a*a - n
b = isqrt(b2)
if b*b == b2:
return int(a - b), int(a + b) # p, q
a += 1
p, q = fermat(n)
assert p * q == n
ברגע שיש p, q, שאר החישוב מיידי. מחשבים את phi, את המעריך הפרטי d, ומפענחים:
from Crypto.Util.number import long_to_bytes
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi) # the inverse of e modulo phi
m = pow(c, d, n)
print(long_to_bytes(m)) # b'close primes leak'
הנה הפתרון המלא כפונקציה אחת:
from gmpy2 import isqrt
from Crypto.Util.number import long_to_bytes
def solve(n, e, c):
a = isqrt(n) + 1
while True:
b2 = a*a - n
b = isqrt(b2)
if b*b == b2:
p, q = int(a - b), int(a + b)
break
a += 1
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
return long_to_bytes(pow(c, d, n))
print(solve(n, e, c))
למה זה עבד ואיך להכליל: להשיג את phi שקול לפרק את n, ו-Fermat מפרק במהירות דווקא כשהראשוניים קרובים - טעות נפוצה מאוד במחוללי מפתחות חובבניים. מקרים אחרים לפירוק: n קטן (מריצים sympy.factorint או שולחים ל-factordb.com), או d קטן (Wiener, ראו למטה). תמיד נסו קודם את factordb - זה חינמי ומיידי אם n כבר ידוע.
פתרון תרגיל 5 - אורקל פענוח והסתרה¶
יש לנו טקסט מוצפן מטרה c שהאורקל מסרב לפענח, אבל הוא מפענח כל דבר אחר. התכונה ההומומורפית של RSA לכפל היא זו ששוברת את ההגנה הזו: (x * y)^e = x^e * y^e. אנחנו "מלבישים" את c בגורם אקראי r, שולחים לפענוח את הגרסה המולבשת (שהיא שונה מ-c, אז השירות מסכים), ומורידים את הגורם בסוף.
choose a random r
c' = c * r^e mod n the blinded ciphertext, different from c
m' = (c')^d = (c * r^e)^d
= c^d * r^(e*d)
= m * r (mod n) because r^(e*d) = r
m = m' * r^(-1) mod n remove r
בקוד, מול מודל האורקל מהתרגיל:
import random
def make_oracle(d, n, forbidden_c):
def oracle(ct):
if ct == forbidden_c:
raise ValueError("refused")
return pow(ct, d, n)
return oracle
# build a key and victim for the demo
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
p, q = getPrime(256), getPrime(256)
n = p * q
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))
m0 = bytes_to_long(b"blind me")
c = pow(m0, e, n)
oracle = make_oracle(d, n, forbidden_c=c)
# the attack itself - without knowing d
r = random.randrange(2, n)
c_blind = (c * pow(r, e, n)) % n # different from c, the oracle will agree
m_blind = oracle(c_blind) # we get m * r mod n
m = (m_blind * pow(r, -1, n)) % n # remove r
print(long_to_bytes(m)) # b'blind me'
למה זה עבד ואיך להכליל: האורקל חשב שהוא מפענח טקסט "לא מזיק" (c_blind), אבל הכפל האקראי היה הפיך לגמרי, אז חילצנו ממנו את המסר של c האסור. אותו טריק בדיוק מזייף חתימות: אם השירות חותם (מעלה בחזקת d) על כל מסר חוץ ממה שרוצים, מלבישים את המסר, מבקשים חתימה, ומורידים את ההסתרה. זו הסיבה ש-RSA גולמי בלי padding תקין (OAEP להצפנה, PSS לחתימה) לעולם לא בטוח מול שירות שמתפקד כאורקל.
נספח - התקפת Wiener למעריך פרטי קטן¶
לשלמות, הנה המימוש המלא של Wiener מההרצאה, למקרה ש-d נבחר קטן (d < n^(1/4)). הרעיון: e/n קרוב מאוד ל-k/d עבור איזה k, ואחד מהמקורבים - convergents - של פיתוח השבר המשולב של e/n הוא בדיוק k/d. עבור כל מקורב בודקים אם הוא מוליד phi תקין שמפרק את n:
from gmpy2 import isqrt
def cont_frac(a, b):
cf = []
while b:
cf.append(a // b)
a, b = b, a % b
return cf
def convergents(cf):
n0, n1 = 0, 1 # numerators
d0, d1 = 1, 0 # denominators
for a in cf:
n0, n1 = n1, a*n1 + n0
d0, d1 = d1, a*d1 + d0
yield n1, d1 # candidate k, d
def wiener(e, n):
for k, d in convergents(cont_frac(e, n)):
if k == 0:
continue
if (e*d - 1) % k != 0:
continue
phi = (e*d - 1) // k
# solve x^2 - (n - phi + 1)x + n = 0 and look for integer roots p, q
b = n - phi + 1
disc = b*b - 4*n
if disc < 0:
continue
s = isqrt(disc)
if s*s == disc and (b + s) % 2 == 0:
return d # found the private exponent
return None
ברגע ש-Wiener מחזיר d, מפענחים ישירות עם pow(c, d, n). שימו לב שההתקפה עובדת רק כש-d באמת קטן - אם היא מחזירה None, d גדול מדי וצריך התקפה אחרת. זו בדיוק הסיבה שבמערכות אמיתיות בוחרים e = 65537 (ואז d גדול), ולא e ענק שמכריח d קטן.