Tags: wiener rsa
Rating:
# Unbreakable (crypto 200)
###ENG
[PL](#pl-version)
In the task we get a list of ciphertexts:
```
4afa32e89fce5fb84c1307e727f117cc999bc443cb646149aecc45df146f50803ca153e101d9b31eee0ac0c3c017b963ef3b74abc528422d08149e2c61a2c83573989368467b3c0696a63686cf4dfd0e8fb7ca943769554f6ddeed6be47a3dbc8695a26f148641619ceac19cd1e62b563711e015aefb0fa8f7868adfb616e406c7
5b1b43f901df61c95d24a8f8381228dd000cd554dc757250bfdd56e125716a9a4db264f2a2e0c42fffabdad4da28c074f14c85bcd639533ea9250f3d72b3d94684090479578c4da707b74797d15e1eaf91c8db05487066517eeffe7cf58b4ecd9706b371259752720dfbd20de2f73c674822fa26bf1ca1b918979be1c727f5a7d8
c494ba812968d951c60b3f8faf900f6622256ccb65ece0c24866cd790ce9d313b640db8030725b088834636b630f52eb89b5fc456da1caa7310c28a6e04a61bdfb212be1cef5b63e2e4ebe1e69c79738195f642cbfe2ddc9e77887e58cf4b7561e2d4ae90c1ec0e026846026708ea5debf00830d489539419f1e14795e0e8c3e6f
d505cb923079e062d7ac4191b10aa17733367ddc76fdfad35977de80adf0e424c75aec9a4a836ca99945747c74a163fc90c61d567eb2dbb842ad39b7fa5b72ce1c323cf2df16c74f3f5fcf2f70d808492061753dc1f3eed0f88998f69d15c8672f3e5bf0ad2fdafa37957a378a9fb6efc1aa94ae59064052012f25806faf9d4f71
e6a6dc034a80fa73e8bd5202c2abb28844478eed871e1be46088ef9abe1af535d86bfd0b5b947db00056858d85b2741d0ad72e678fc3ecc953be40c81b6c83df2d434d13e127d8514161d1318ae9a9503a72864ed214ffea199009170e26d978314f6c1abe31eb1b48068b489b01c7f1d2bb05bf60a75a63a231369a71b10e5182
f7b7eda45b9a1b84f9ce63a3d3bcc39955589ffe982f2cf57a99f10bcf2b1646e97c1eac6c058ecaaa67969e96c3852eabe83f7891d4fdd064cf5ad92c7d94e13e545e24f238e9625272e2429bf0b06a4b83975fe32511fb200aa028af37e08942517d2bcf42fc2c59a79c590ca2d812e3cca6c17ab86b74b342470b82c2af6293
a272096ef746b73ea4801d6d9d788d44fff34aa043cac8af2644ab578ac7b1e10428b068185f308666124140418d3fc06703da234b9ea9951e8af694c8294e0bd0fef0ceacd3041cfc2c0cec47a57516e73d42fa0dcfbba7c55665c36ad20534ecfb29c78aeca8c8f46248f4586c93bc0d88618b2673172e7dece2573c8c6a1c4d
b383a07f1857c84fb59a2e7e0e899e5511145bba54dbd9b13755bc689bd8c2f2a539ca7929614a977723525a529e41da78a4eb345c0fb0062f9b1705d9305facea1f1adfbde4a52d1d3dadfd58b68627f84e531baed1ccb8d66776d47be3a645fd1c30d89bfdb9d915735915697d04cdae99729c3784283f8efdf3684d9d7b2d5e
18c8feb56c0b2c9510df74b4e4cdd4006669011f09313d168b0012acd13c2757f08d2fbd7da69fdbbb78070f07d4963fbcf9418902e51eea75d16be03d8e05f24f656f351349f0736383f3530c1aca7b5c940861f436221c3aabba39b148fa9053628e3cd1531d3d60b80d60adb3e923f4ddb7d28bc97c85c45358ac93d3b17304
29d91fc67dac3d062ae185c5f5dee5aa7770a221a0424e279caa23bde24d38681a9e31ce8eb701eccc89a8a1a8e50741cd105290a3f62ffb86e27cfa4e9fa6135176714624501a8474941464ad2bdb8c6d05a9721547332d4bbccb40c2591b0a64739f4de2642e4e7ac9ae7abec4f03415eec8e39cd08d96d56469bd04e4c284a5
30e021d78ebd4ea73bf296d616eff6bb888ab332ba535f380dbb34cef35e49792b0f42df9fc8a2fddd90b9b2b9f6a852de2a630ab417311c97f38d1b5f01b72462878257356a2b9585052575be3cec9d7ea6b0832658443e5ccddc5ad3602cab7584015ef3753f5f8bd0bf8bcfd51a4526ffd9f40dea9e07e67570cea5f5d395b6
6c2c5410a2e172d06e35b919492339eeaaade665ed86836ac1ee67f236827b0b5ec37513b3fad53111bcebe5eb39da85125d96cde740644fb036a14e83c4e05795a0a580689d5eb8a8c85808e26f2fb102d9eca6598a77628ff11f8d169c5fde08a7c48236086383ae1ce3aef3184d7859331b37c12db2c029080cf2d83816b8e9
7d3d652ab3f283ea7f46c020503440ffbbbef776fe97947bd2ff781347938cac6fd48624c41be64222cdfcf6fc40eb96236e07def85a7551ca47b25f94d5fa6806bab69a790e6fc9b9d969a9f37131c2a3e0fdb7609b88739112219e270d61efa9b8d59347a97494bf2df4bf14295e8960442c48d23ec3da30a9ad13e94927c9f0
8e4e763bc41394fb8157da3a6a455a11cccf18871f08058ce311892458049dbd71e59735d52cf75333de1d171d5afc07347fa8ef196b8662db58c36105e61b79a7cbc70b80af71d0c0e070b0148242d3b4fa1ec87a0c99840223320f38ae72f1b0c9e60458b08505c13e15c125306f907a553d59e34fd4eb4ab0be24f05038d01a
9f5f874cd524051c9268eb4b7b566b22ddd1299821a9a69df422903569a50ece82f60846e63d186444ef2e282e6b1da84581b9f1207c9773ec69d472a6f72c80b8dcd8ac9ab182eadafa8aca259353e4c51b2fd98bad0095a33443a149bf8312cad0f7a569ca96a6d24f26d2364a710a8b664e60f451e5fc5bcacf351a6a49ea2b
```
RSA public key:
```
-----BEGIN PUBLIC KEY-----
MIIBIDANBgkqhkiG9w0BAQEFAAOCAQ0AMIIBCAKBgQJv2xhIxiuhHjnor5wSIRKv
2N9SPlfz4OARJP7pK+1P6+Deh6OwMwKI8PNfu82IsCyLRh7QLE6vv6pidMRcAl5f
8xXGTrKO2jeDobGuaU5iUJFCZaqTk+P4oqPfPasZFSt5b61Ry8gHm0duznl5oBvw
WgU3jIThczwB4OJvlqyxvQKBgQHWX/1eQndrZGyltFAAcklgmddKdq6YKd83LYJp
j88ZYXdud5ZvbfgisxIP5dfSb/O71nK97XRRvwrmEQhIlWhJEHPhsRZnaxrXl3v9
Cs1g+iRZIlbGbOiO5YyY3rv6bJRQAlVieDQAH/DS4aQ23v0hw4C8U/P2fe70EA6Q
KChwew==
-----END PUBLIC KEY-----
```
And some custom function which was used on top of RSA to encrypt the ciphertexts:
```python
def unbreakable(plaintext, shift):
alphabet = ["a", "b", "c", "d", "e", "f", "1", "2", "3", "4", "5", "6",
"7", "8", "9", "0"]
dic = {}
for i in range(0, len(alphabet)):
dic[alphabet[i]] = alphabet[(i + shift) % len(alphabet)]
ciphertext = ""
for l in plaintext.lower():
if l in dic:
l = dic[l]
ciphertext += l
return ciphertext
```
We start off by breaking the RSA public key.
We can see that the parameters are:
```
e = 330308529733985078905192489170457797127445873886898886884167097632004156404145841905155557293348697562191247181138098211415966471442518825658480167379206235599206895852734016511083329346348463780299199626557639461008110628563442507362604398459446042070313485121763459101281714995771633784632378550465577119867
n = 438086468535501215559099821943641565440163837859843437360994716558082080505682672423625729340496687893196218594088978020343109764032002743133493845164774889396516790921601420834111428144281957595107296011951640484375132818685917451714669162950174081376950570372632914428315670385863665730062358610049531425213
```
And such a big `e` mean it is vulnerable for Weiner attack.
So with Sage:
```sage
e = 330308529733985078905192489170457797127445873886898886884167097632004156404145841905155557293348697562191247181138098211415966471442518825658480167379206235599206895852734016511083329346348463780299199626557639461008110628563442507362604398459446042070313485121763459101281714995771633784632378550465577119867
n = 438086468535501215559099821943641565440163837859843437360994716558082080505682672423625729340496687893196218594088978020343109764032002743133493845164774889396516790921601420834111428144281957595107296011951640484375132818685917451714669162950174081376950570372632914428315670385863665730062358610049531425213
c_fracs = continued_fraction(e/n).convergents()
test_message = 42
test_message_encrypted = pow(test_message,e,n)
d = 0
for i in xrange(len(c_fracs)):
if pow(test_message_encrypted,c_fracs[i].denom(),n) == test_message:
d = c_fracs[i].denom()
break
print(d)
```
We recover the decryption exponent `d = 41120410289578972492231832470931555317369771850118171981275077778106071589823`.
Now we need to invert the `unbreakable` function, but this is rather trivial:
```python
def unbreakable_rev(ciphertext, shift):
def get_key(c, dic):
for key, value in dic.items():
if c == value:
return key
return c
alphabet = ["a", "b", "c", "d", "e", "f", "1", "2", "3", "4", "5", "6",
"7", "8", "9", "0"]
dic = {}
for i in range(0, len(alphabet)):
dic[alphabet[i]] = alphabet[(i + shift) % len(alphabet)]
plaintext = ""
for c in ciphertext:
plaintext += get_key(c, dic)
return plaintext
```
So with those two things at hand we can decrypt the ciphertexts:
```python
n = 438086468535501215559099821943641565440163837859843437360994716558082080505682672423625729340496687893196218594088978020343109764032002743133493845164774889396516790921601420834111428144281957595107296011951640484375132818685917451714669162950174081376950570372632914428315670385863665730062358610049531425213
d = 41120410289578972492231832470931555317369771850118171981275077778106071589823
with codecs.open('flags.txt', 'r') as input_file:
for i, line in enumerate(input_file):
line = line[:-1]
unb = int(unbreakable_rev(line, i + 1), 16)
p = pow(unb, d, n)
print(i, long_to_bytes(p))
```
There a small twist here that for some reason (we were missing 1 of 16 ciphertexts) we were supposed to shift the unbreakable argument by +1.
Anyway, by running this we get the flag: `{RS4_wi3n3r_vuln3r4ble}`
###PL version
W zadaniu dostajemy listę ciphertextów:
```
4afa32e89fce5fb84c1307e727f117cc999bc443cb646149aecc45df146f50803ca153e101d9b31eee0ac0c3c017b963ef3b74abc528422d08149e2c61a2c83573989368467b3c0696a63686cf4dfd0e8fb7ca943769554f6ddeed6be47a3dbc8695a26f148641619ceac19cd1e62b563711e015aefb0fa8f7868adfb616e406c7
5b1b43f901df61c95d24a8f8381228dd000cd554dc757250bfdd56e125716a9a4db264f2a2e0c42fffabdad4da28c074f14c85bcd639533ea9250f3d72b3d94684090479578c4da707b74797d15e1eaf91c8db05487066517eeffe7cf58b4ecd9706b371259752720dfbd20de2f73c674822fa26bf1ca1b918979be1c727f5a7d8
c494ba812968d951c60b3f8faf900f6622256ccb65ece0c24866cd790ce9d313b640db8030725b088834636b630f52eb89b5fc456da1caa7310c28a6e04a61bdfb212be1cef5b63e2e4ebe1e69c79738195f642cbfe2ddc9e77887e58cf4b7561e2d4ae90c1ec0e026846026708ea5debf00830d489539419f1e14795e0e8c3e6f
d505cb923079e062d7ac4191b10aa17733367ddc76fdfad35977de80adf0e424c75aec9a4a836ca99945747c74a163fc90c61d567eb2dbb842ad39b7fa5b72ce1c323cf2df16c74f3f5fcf2f70d808492061753dc1f3eed0f88998f69d15c8672f3e5bf0ad2fdafa37957a378a9fb6efc1aa94ae59064052012f25806faf9d4f71
e6a6dc034a80fa73e8bd5202c2abb28844478eed871e1be46088ef9abe1af535d86bfd0b5b947db00056858d85b2741d0ad72e678fc3ecc953be40c81b6c83df2d434d13e127d8514161d1318ae9a9503a72864ed214ffea199009170e26d978314f6c1abe31eb1b48068b489b01c7f1d2bb05bf60a75a63a231369a71b10e5182
f7b7eda45b9a1b84f9ce63a3d3bcc39955589ffe982f2cf57a99f10bcf2b1646e97c1eac6c058ecaaa67969e96c3852eabe83f7891d4fdd064cf5ad92c7d94e13e545e24f238e9625272e2429bf0b06a4b83975fe32511fb200aa028af37e08942517d2bcf42fc2c59a79c590ca2d812e3cca6c17ab86b74b342470b82c2af6293
a272096ef746b73ea4801d6d9d788d44fff34aa043cac8af2644ab578ac7b1e10428b068185f308666124140418d3fc06703da234b9ea9951e8af694c8294e0bd0fef0ceacd3041cfc2c0cec47a57516e73d42fa0dcfbba7c55665c36ad20534ecfb29c78aeca8c8f46248f4586c93bc0d88618b2673172e7dece2573c8c6a1c4d
b383a07f1857c84fb59a2e7e0e899e5511145bba54dbd9b13755bc689bd8c2f2a539ca7929614a977723525a529e41da78a4eb345c0fb0062f9b1705d9305facea1f1adfbde4a52d1d3dadfd58b68627f84e531baed1ccb8d66776d47be3a645fd1c30d89bfdb9d915735915697d04cdae99729c3784283f8efdf3684d9d7b2d5e
18c8feb56c0b2c9510df74b4e4cdd4006669011f09313d168b0012acd13c2757f08d2fbd7da69fdbbb78070f07d4963fbcf9418902e51eea75d16be03d8e05f24f656f351349f0736383f3530c1aca7b5c940861f436221c3aabba39b148fa9053628e3cd1531d3d60b80d60adb3e923f4ddb7d28bc97c85c45358ac93d3b17304
29d91fc67dac3d062ae185c5f5dee5aa7770a221a0424e279caa23bde24d38681a9e31ce8eb701eccc89a8a1a8e50741cd105290a3f62ffb86e27cfa4e9fa6135176714624501a8474941464ad2bdb8c6d05a9721547332d4bbccb40c2591b0a64739f4de2642e4e7ac9ae7abec4f03415eec8e39cd08d96d56469bd04e4c284a5
30e021d78ebd4ea73bf296d616eff6bb888ab332ba535f380dbb34cef35e49792b0f42df9fc8a2fddd90b9b2b9f6a852de2a630ab417311c97f38d1b5f01b72462878257356a2b9585052575be3cec9d7ea6b0832658443e5ccddc5ad3602cab7584015ef3753f5f8bd0bf8bcfd51a4526ffd9f40dea9e07e67570cea5f5d395b6
6c2c5410a2e172d06e35b919492339eeaaade665ed86836ac1ee67f236827b0b5ec37513b3fad53111bcebe5eb39da85125d96cde740644fb036a14e83c4e05795a0a580689d5eb8a8c85808e26f2fb102d9eca6598a77628ff11f8d169c5fde08a7c48236086383ae1ce3aef3184d7859331b37c12db2c029080cf2d83816b8e9
7d3d652ab3f283ea7f46c020503440ffbbbef776fe97947bd2ff781347938cac6fd48624c41be64222cdfcf6fc40eb96236e07def85a7551ca47b25f94d5fa6806bab69a790e6fc9b9d969a9f37131c2a3e0fdb7609b88739112219e270d61efa9b8d59347a97494bf2df4bf14295e8960442c48d23ec3da30a9ad13e94927c9f0
8e4e763bc41394fb8157da3a6a455a11cccf18871f08058ce311892458049dbd71e59735d52cf75333de1d171d5afc07347fa8ef196b8662db58c36105e61b79a7cbc70b80af71d0c0e070b0148242d3b4fa1ec87a0c99840223320f38ae72f1b0c9e60458b08505c13e15c125306f907a553d59e34fd4eb4ab0be24f05038d01a
9f5f874cd524051c9268eb4b7b566b22ddd1299821a9a69df422903569a50ece82f60846e63d186444ef2e282e6b1da84581b9f1207c9773ec69d472a6f72c80b8dcd8ac9ab182eadafa8aca259353e4c51b2fd98bad0095a33443a149bf8312cad0f7a569ca96a6d24f26d2364a710a8b664e60f451e5fc5bcacf351a6a49ea2b
```
Klucz publiczny RSA:
```
-----BEGIN PUBLIC KEY-----
MIIBIDANBgkqhkiG9w0BAQEFAAOCAQ0AMIIBCAKBgQJv2xhIxiuhHjnor5wSIRKv
2N9SPlfz4OARJP7pK+1P6+Deh6OwMwKI8PNfu82IsCyLRh7QLE6vv6pidMRcAl5f
8xXGTrKO2jeDobGuaU5iUJFCZaqTk+P4oqPfPasZFSt5b61Ry8gHm0duznl5oBvw
WgU3jIThczwB4OJvlqyxvQKBgQHWX/1eQndrZGyltFAAcklgmddKdq6YKd83LYJp
j88ZYXdud5ZvbfgisxIP5dfSb/O71nK97XRRvwrmEQhIlWhJEHPhsRZnaxrXl3v9
Cs1g+iRZIlbGbOiO5YyY3rv6bJRQAlVieDQAH/DS4aQ23v0hw4C8U/P2fe70EA6Q
KChwew==
-----END PUBLIC KEY-----
```
I jakąś autorską funkcje użytą jako dodatek do RSA:
```python
def unbreakable(plaintext, shift):
alphabet = ["a", "b", "c", "d", "e", "f", "1", "2", "3", "4", "5", "6",
"7", "8", "9", "0"]
dic = {}
for i in range(0, len(alphabet)):
dic[alphabet[i]] = alphabet[(i + shift) % len(alphabet)]
ciphertext = ""
for l in plaintext.lower():
if l in dic:
l = dic[l]
ciphertext += l
return ciphertext
```
Zaczynamy od złamania klucza publicznego RSA.
Widzimy że parametry to:
```
e = 330308529733985078905192489170457797127445873886898886884167097632004156404145841905155557293348697562191247181138098211415966471442518825658480167379206235599206895852734016511083329346348463780299199626557639461008110628563442507362604398459446042070313485121763459101281714995771633784632378550465577119867
n = 438086468535501215559099821943641565440163837859843437360994716558082080505682672423625729340496687893196218594088978020343109764032002743133493845164774889396516790921601420834111428144281957595107296011951640484375132818685917451714669162950174081376950570372632914428315670385863665730062358610049531425213
```
A tak duże `e` jest podatne na atak Wienera.
Więc za pomocą Sage liczymy:
```sage
e = 330308529733985078905192489170457797127445873886898886884167097632004156404145841905155557293348697562191247181138098211415966471442518825658480167379206235599206895852734016511083329346348463780299199626557639461008110628563442507362604398459446042070313485121763459101281714995771633784632378550465577119867
n = 438086468535501215559099821943641565440163837859843437360994716558082080505682672423625729340496687893196218594088978020343109764032002743133493845164774889396516790921601420834111428144281957595107296011951640484375132818685917451714669162950174081376950570372632914428315670385863665730062358610049531425213
c_fracs = continued_fraction(e/n).convergents()
test_message = 42
test_message_encrypted = pow(test_message,e,n)
d = 0
for i in xrange(len(c_fracs)):
if pow(test_message_encrypted,c_fracs[i].denom(),n) == test_message:
d = c_fracs[i].denom()
break
print(d)
```
I odzyskujemy wykładnik deszyfrujący `d = 41120410289578972492231832470931555317369771850118171981275077778106071589823`.
Teraz musimy jeszcze odwrócić funkcje `unbreakable` co jest dość trywialne:
```python
def unbreakable_rev(ciphertext, shift):
def get_key(c, dic):
for key, value in dic.items():
if c == value:
return key
return c
alphabet = ["a", "b", "c", "d", "e", "f", "1", "2", "3", "4", "5", "6",
"7", "8", "9", "0"]
dic = {}
for i in range(0, len(alphabet)):
dic[alphabet[i]] = alphabet[(i + shift) % len(alphabet)]
plaintext = ""
for c in ciphertext:
plaintext += get_key(c, dic)
return plaintext
```
Majac te dwa elementy pod ręką możemy odszyfrować dane:
```python
n = 438086468535501215559099821943641565440163837859843437360994716558082080505682672423625729340496687893196218594088978020343109764032002743133493845164774889396516790921601420834111428144281957595107296011951640484375132818685917451714669162950174081376950570372632914428315670385863665730062358610049531425213
d = 41120410289578972492231832470931555317369771850118171981275077778106071589823
with codecs.open('flags.txt', 'r') as input_file:
for i, line in enumerate(input_file):
line = line[:-1]
unb = int(unbreakable_rev(line, i + 1), 16)
p = pow(unb, d, n)
print(i, long_to_bytes(p))
```
Był tam mały szkopuł, bo należało argument funkcji odwracającej unbreakable przesunąć o +1 (bo niby brakowało nam 1 z 16 ciiphertextów).
Tak czy siak uruchamiając powyższy kod dostajemy: `{RS4_wi3n3r_vuln3r4ble}`
