Daily AlpacaHack: a fact of CTF Writeup

a fact of CTF

AlpacaHack で一番最初に完成したものの難易度調整により出題されなかった幻の問題 （運営コメント）

import os


flag = os.environ.get("FLAG", "not_a_flag")

# all prime numbers less than 300
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]
assert len(flag) <= len(primes)

ct = 1
for i, c in enumerate(flag):
    ct *= primes[i] ** (ord(c))

print(hex(ct))

暗号文は以下の数式に従って生成されます。

\mathrm{ct} = \mathrm{primes[i]}^\mathrm{flag[i]}  

つまり、i番目の素数を取り、それをi番目のflag文字で累乗することにより暗号文が生成されています。

解法

例えば、2をord('A')で累乗を取ってみましょう。
ord('A')は65なので、$2^{65}$となり、36893488147419103232となります。

>>> print(ord('A'))
65
>>> print(2**ord('A'))
36893488147419103232

ということは、累乗の値を取り出すには36893488147419103232が2で何回割れるかをカウントしたら良いです。

exp = 0
ct = 36893488147419103232
p = 2
while ct % p == 0:
    ct //= p
    exp += 1
print(exp)
#65

このことから、i番目の素数が何回割り切れるかを確認することでフラグを復元することができます。
以上の操作を実装すると、以下の通りになります。

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]
ct_hex = "0xadb88e47d531cdb104013d7aa8a21e6f5bfb841d2ff5d5090d735f9a1d9f6bb2dc0ad6d19efca47ec943e5a8b685f295be56d3531fcb49e41d5d02dd6113e3fcd369a5c25098b38e540fc865e2f1078292efc89778b5f29e74b188c87afcdeb9f4c58d77d1314271646bc1043c63e62b76396f1349b914a0d489df9c211c6e551969694c1a930f8e04379a589869c4a838d0db71168f61b8ff38c6107fca44d2b5064ed42a4b8bbd774025f43907275317679daa0fb58e4127eac72eedb6be263fc0897f6d791eb3b301321b1e0ed37234b92249fe164f5b1a85981e7b52d65e50315520bfcf9c45f86e6d9c899e7aaefa936fa1a7f14dbb9bc9d9615dc9d97e7aecf162549866488b99d6903586f0cbdabfa0de664e66b8e36dadc2fec12d09a6ac3d33b6cdd8aaeccf58f7a3abbc2bcce34652f08617b33583568a1c5335a13d1530c69284d13df513314aa5b12db052529faf61461107d088008658730bce9af8ac9a9b262df3f1e9c84334f3616e9ed9d6598c4a70e9894b47ad73b415713371a5ced21f2853e02f0cce55969ff3101fb9da00c6f48932fa8696ee474bee89d462e08038566ea125f56733f029f40d13ea98a92ddbfcd7b0c900e8b1c7bc65124ae620279e7ae00fb8ef65f835665e344d570325330f90c85326571fd96ba2883fc7b2b6615f35d555948acf3c0ae684a0af323011d209dd8374649dec9bbdaa0ab7068af63fdaacbc5177fd75b457e91fec461a33a0fcb55754d655f2fb9e198d81df64009e9e1e34bddb349955d0792d9717161ba4538b564d85fb6630e2acb4bc95130f6c9d31d6f53aeaecd4c023c50df0b8e2e50c84db4051261abaf38f7020b2964ba6ad05932e22428ae773e78dc83014e674261859b65bd7c9d4b328dd9abbae1067f735006d4400f8c595ee01904fcbdf54c34f983826c24876877f76b9ee14327ddb6b7a7a2625a65a92c2ea757f42d0a3a6fb824d00c9ad4fb4cb2b2c77b0d66b89fc4846b5448df3bfa8977a8e42e9ea4ec5948264f0cd8efeec387c0344b56017657679605b1d0bc32fb1742b1cb8f2426e35e1e673c6af6ae5f3d3bda56b4de192f994f3aef809ae92dda1ab20aef0a948c9bdfecb896727856a0d8a0d9af81661ba53c7927223b2389a168c8adc04f1e7a07499d308bf9cdbe55220a5fa392879d644f3c25949c7d4d6aee482525ad22c3bde07e16fcc1788362bf365c0e12db42e0ad2ce29d666bed43f24dadfec45008b6c1dd96649c2afbbd392e635b5185fe5c8f9374eb6c7418cd5c4400a8025eb989e1ca66943e02e7d54b2744c51e17de2a919972c7deac0735501ce812b9453e2e14d22ec1dd2e87af06d47e8118c27a6357e006d774f053f977619347b62c6f01bf810369924295c4e097a6e8586eef1e310e787d870b0c4bee2e0d0a63b1dde4ef656213788dad7214e61d76c5b850c13836fc35ce85840ca5c450459753295ed628af60fb102c26208ac7bd09f5b02f9b4800eb486e41e4bfe780e02993a3259a5e310b404069bc15d2230b26a7f5e3d53df96ece4d51086444cb5bd24fb507f31869b248facccff49d5cf43643013f144af758c41405a02fd70564bea480b3a157059c1fab45e89bfd7caf543e2605d0d7e06ddb343cf2d03377355a12d818b430b8614687834a37bb0442197d9803fdab84129c864708031959b99abebbe013c221f5397d25750a9b8fd7d004a017646f0792c87ade48e6138bd554fdb2df57b980bdb073c805f99754affbcca377a37c9383c68add373c879ab309efc144234a1b55b44012bc5fad42e2b9c7ca13421cffb68b3dbfe6d5b6d009e02ae27bd45203c1db0bf250c22ffbc689f21b8b503ca5091465ef28295e307084cffb00f3af88bb0ffecaaa10496c866aceedd97059731b6defc3501b399ad7b8ff57f66872ad49573df06aeffe097ae904914d78991ba6008de217fb7f766044ab7a1fd79878f87df9fb3ad74024bfadc4a3a781216b141e2ac6c34ce76f0cf60a33a0c44a9a31770c279e7b11b87380de18406b5cd7c4892cb49ff5a8ef07c95a4c669eff91f424308342f68bb558c240c8a66393a561d659ada61b0fd595a155bca28054b13fe3aef57ba3fff5a39c92c0f4b8c5e3f8ef8aaa27aef70c1a065d10c107f2354f117b7f00db658326e07b8c3c6c833a3742a98a99e40ec978b71c656612da7c232575685e0f00c4fa51c0f13d064798b82db23a192bb6b8db0319fc3924929b350fbef650395d408df85e6fc5b63294ea8f36f98473f5a4b273e1a0a4b9545512547e8aabe1381989b6e241d47fd121f51478829a6557ab83bfa3579940c2d08201b24b09d209928f3914672ae60d1be1aa1dd20d7908d68da91c49523109a64bc553b4d89aa704f1628c9cca45b2ad157a874eb3afbd7d5e34bc958bf46bd455b2899a3033743af16d467eda2fd0c9b7f8892a82a8763c41c1fb112f2ecad17ae30da44db3d8f8a9a61510354fc5e072fe12b556f98edb933c9319e232451fa422d7cfed27af993fdd40913c6ddbfe9a89f1ae37c7ee8c2b058870daa04127f56ad5acafdb6accfd9fe66b49d653a39ccecf3dbade95b7eea178fdc82a7e6e5e3f118c9b800f96ab85a9109379dbf56a84ffe6fad6fc3bda0bc9968e231d34aacd5bb8c7f72630ca9cba7d7764c8abe5aa545cf9975dc163302ceee56865e4306accc9011e80134378f131fb6255c8af6d2d94d5f3e73b3c0cd2c6a86fd97e016641ea05bb61f97d701e413ecc376c07395fa5b7d615c6a32cc3fd3cad5669c925bedacf102f1f611f82a157a7362c01c095432c13e75707605e07d39d6caaa1693b06e266fbeb29be640125361071fa98c6e9c236c12ca5d0c88ad45ab8e2d6d2962ea454c30572d6347b13670d4ee9f75e1c17a71edd79fbd0c58ff3ba2eec6a5cd017187fb85cb396490012155ec40a2f002a38dca1396affafd43b6fa28f54e42eaef83982f4050b8c70b6091e07a08ac8d5b74bd7cd2fc86014e174e8d1f53cfd9277858ed4e16833daf3fb4902b8b782d7bab0cdabcfa6c0d922baf5cefa7bc110434a474d9de2c3312ddd7cf457a837cd762d2f3444054ff7389d81bc52a6bdb9731bd34a77f48bc8fc383f1bdd46ef5666df0d2f41ba359c8168ae5bd0d5ec36a85b9ec5a1469af81ef4f5254fb4b0e7d31c64ea4fc9975f157872b7f178d792877be60a014622a7594746017fea2e8c50926a36c0294249cd2d1b3ffb060eaa8050b906f4adb6acbf8446e9b22256d3e32dc63dbde922f0296b66d57c32f4d8ad5382d3159f787e4474f48a5d1033ba4760b9f74b66751efc7375b48c55ab3817458ca71ac52b8360da2f512f247e4b99fea2a43f423fcd76bfb9e64a2a0fcd69a3876c517ecaab5a4efffa8e957ba647eea810953e1554345872488a7b7b60735689c20e3ac9d5345c935bfaf80c3a6fafd1cd551457e3f8c4caa24568443b5afd0bd6eeda07938838bcb946460c9e882b3af29ca787b7a0b03ac3318cd720f7b08169096aee70c26bb59f3fcb39fef1d02140f43c4e6ba06e8eaf87f20685962fbbf1609216be320168e05b3ea734687779e8453ee4b44e793ccce8a541ec26781d980a58ec6625f194b7485bfd980f61ddcdc18626cc60b7754951520256f1676a35b64ee4d3f46c8a992fd824a425019b90c5ceb90c5feec0d3ba970f46cb5736f8e2673fabc8b40ea71730ca6e7dc45efff9126528f3e8c976ae1c1c2a9ed1f09fc848e986a8e2a771865424a16f8f3f8fd86e5c9c7bec7f7f698ddcd45b33f7b82b2973b075e46b07d415f50a845eb214d49f975b03c471fa4f8bd3c73261c4037eed7815f388c4e454737cff44fa12d358336ad5f0f8df8da4ba572a0e71012bcb776c41ea29bbab45c2645c880d4108f1de20a867464513414d5aeab3621a2cc08ce9370a2d64a0dbc0aff5f0722cdabfc3d90dfc2ac63b65f4a6e9111ae0595b1c03e7d55d16449d6f8b1ae6328cd3b29189ed9eb34ad5b1541f8596f302d0254c32ee04a555d1ba9567c47fafdfdb05b98783e04d2052d4594f8c7549b048c11477229228e3be8cdb214218e9069a2f21ed370b12df6708357db5b3e8dbf1895ea167c77ec4b6beb93fa7d6fb61737b61beffadf5f3b533be8730caec2ef1fe47bbee3d204ae007bd2c0b7a1c1784a71e0d85d6317111079a5d4e74c62304f6c91ba32b8e5f62ac68811cc0d67d9707173129c5ce874d6d52c1178b6eb86a739df6c27020ebb489224f1d5ca08ada416f5dad9f224a795b475ceca4fedceef605e96c5cb939ec6c361463bc86bdfc6c5c5f24b42888b59e229082b024f78eb28b9190beb46a2802dfef1f9019511118cd8dd338b1e3ac04235cb6a31afb49b27fee71da3a387a1904acd74799ce5211e3c2c43b66ad6a050b70b28a2dac3294abc1d53cb9df334546ef70f7aa29e93a0902fd23b0a554570e0271a49b8c548b5cf846c04f80dd922749b53f4f0db901e4c97c1209236adf891e184564a6b94f3da00e2fb548fb581c204eec117f8381a735f2fcecfd69c31d15342b053d5681fc97644c51e604f99299c7679727b25f73d863f83e0bc2288255af7c0720bd3b0f1820e60895a0d37f60ee05b928f7311f97434dd527fc2f4a33c8d0f4e4e3f7e160afa1a2731c522eef280702dd4eba358370cd6c9386c196d351f2ef8935045efb196d6b6a11e42209f0a4b64f4aea7b830ee131bd46d33d36f42dcfe833e5fddf59ea417c5ddb8a80c50957e3eec9177277483d1231d0e5f40aea3bfa9eec670bf19a72e0b96a3f9be8a8c63cca7960c374d2196881aafef24d32b2d582bd562dfd8d1996f1e7f73e412e3690ae5a492e11d173f04ba9e68d8d9cfaaf322eec828f95be3fe7e4c8dfc156993edb40321d40fb59cba71775581b2186fdd0271c04d85373e1022be81e21998a360bc1ba46dfd69bfb4dbedf43f9688483cab2002de982ec8e9ced314aac88b37694fcb63a41b7f245425c0455c146dfad31cd56174e92fcc6eb7e0000000000000000"

ct = int(ct_hex, 16)

flag_chars = []

for p in primes:
    exp = 0
    while ct % p == 0:
        ct //= p
        exp += 1

    flag_chars.append(chr(exp))

flag = "".join(flag_chars)

print(flag)

Flag: Alpaca{prime_factorization_solves_everything}