この大会は2021/5/22 14:00(JST)～2021/5/23 14:00(JST)に開催されました。
この大会はチーム戦でしたが、1人チームで参加。結果は1811点で943チーム中76位でした。
自分の弱点を強化するための1人チーム参戦なので、結果はあまりよくないですが、勉強にはなりました。
今後のためにも自分の解けた問題をWriteupとして書いておきます。
welcome (welcome)
Discordに入り、#announcementsチャネルのメッセージを見ると、フラグが書いてあった。
ctf4b{Welcome_to_SECCON_Beginners_CTF_2021}
git-leak (misc)
$ cd .git $ cat refs/heads/master e0b545f42cd1b3d51defe4cf6fe235f143e73d93 $ cat logs/HEAD 0000000000000000000000000000000000000000 c27f346b227d2ac4d267dcdb26d14ff6d9e9f365 task4233 <29667656+task4233@users.noreply.github.com> 1620483366 +0900 commit (initial): initial commit c27f346b227d2ac4d267dcdb26d14ff6d9e9f365 656db59e6f8afccfccbe80a2826ed28cecad8b36 task4233 <29667656+task4233@users.noreply.github.com> 1620483390 +0900 commit: feat: add README.md 656db59e6f8afccfccbe80a2826ed28cecad8b36 6d21e224d5c7c952797a0a7c6a8e456eda8f2bf6 task4233 <29667656+task4233@users.noreply.github.com> 1620488159 +0900 commit: feat: git addの説明を追加 6d21e224d5c7c952797a0a7c6a8e456eda8f2bf6 9fcb00646c821ae57679ad7564a611dbf2f56245 task4233 <29667656+task4233@users.noreply.github.com> 1620488580 +0900 commit: feat: git commitの説明追加 9fcb00646c821ae57679ad7564a611dbf2f56245 a4f7fe94c8c5a710e65a040557eddbe9512bc7ee task4233 <29667656+task4233@users.noreply.github.com> 1620488745 +0900 commit: feat: git logの説明を追加 a4f7fe94c8c5a710e65a040557eddbe9512bc7ee d5aeffe8052a0fde365005c18cc5ce77372df28d task4233 <29667656+task4233@users.noreply.github.com> 1620489336 +0900 commit: feat: resetの説明を追加 d5aeffe8052a0fde365005c18cc5ce77372df28d f66de64cb24616fe4e8b2cce9adf9b8648dbef83 task4233 <29667656+task4233@users.noreply.github.com> 1620489506 +0900 commit: feat: reflogの説明追加 f66de64cb24616fe4e8b2cce9adf9b8648dbef83 d3b47fe3fc6fd790e1dc4bf261f75cd9d55bb099 task4233 <29667656+task4233@users.noreply.github.com> 1620489901 +0900 commit: feat: fsckを追記する d3b47fe3fc6fd790e1dc4bf261f75cd9d55bb099 8fc078d4d404e2ae9b9e10c94a63d459c1f973ef task4233 <29667656+task4233@users.noreply.github.com> 1620490469 +0900 commit: feat: git cat-fileの説明を追加 8fc078d4d404e2ae9b9e10c94a63d459c1f973ef 9ac9b0cdcde2e15a05764062117d81442a9cb4f5 task4233 <29667656+task4233@users.noreply.github.com> 1620490513 +0900 commit: change: 順番を変更 9ac9b0cdcde2e15a05764062117d81442a9cb4f5 36a4809f1ae8013432eb52cfd2f9f062a3269499 task4233 <29667656+task4233@users.noreply.github.com> 1620490831 +0900 commit: feat: commit-treeの説明を追加 36a4809f1ae8013432eb52cfd2f9f062a3269499 73879828a8ecac85c705508cdc9398f26c697249 task4233 <29667656+task4233@users.noreply.github.com> 1620491725 +0900 commit: feat: めもを追加 73879828a8ecac85c705508cdc9398f26c697249 73879828a8ecac85c705508cdc9398f26c697249 task4233 <29667656+task4233@users.noreply.github.com> 1620491734 +0900 reset: moving to HEAD 73879828a8ecac85c705508cdc9398f26c697249 36a4809f1ae8013432eb52cfd2f9f062a3269499 task4233 <29667656+task4233@users.noreply.github.com> 1620491768 +0900 rebase -i (start): checkout HEAD~2 36a4809f1ae8013432eb52cfd2f9f062a3269499 73879828a8ecac85c705508cdc9398f26c697249 task4233 <29667656+task4233@users.noreply.github.com> 1620491768 +0900 rebase -i: fast-forward 73879828a8ecac85c705508cdc9398f26c697249 b3bfb5c80e48bba23ab820ff91442cc3800c393a task4233 <29667656+task4233@users.noreply.github.com> 1620491811 +0900 commit (amend): feat: めもを追加 b3bfb5c80e48bba23ab820ff91442cc3800c393a b3bfb5c80e48bba23ab820ff91442cc3800c393a task4233 <29667656+task4233@users.noreply.github.com> 1620491834 +0900 rebase -i (finish): returning to refs/heads/master b3bfb5c80e48bba23ab820ff91442cc3800c393a 80f3044ec17bd6be63f428e87e0a5fce690c50c5 task4233 <29667656+task4233@users.noreply.github.com> 1620491866 +0900 commit (amend): feat: めもを追加 80f3044ec17bd6be63f428e87e0a5fce690c50c5 e0b545f42cd1b3d51defe4cf6fe235f143e73d93 taro hoge <taro@secc0n.jp> 1620491902 +0900 commit (amend): feat: めもを追加 $ python -c 'import zlib; print zlib.decompress(open("objects/73/879828a8ecac85c705508cdc9398f26c697249").read())' commit 276tree a5b6b52f47aba96730ab61471ddcdff864e5dd8c parent 36a4809f1ae8013432eb52cfd2f9f062a3269499 author task4233 <29667656+task4233@users.noreply.github.com> 1620491725 +0900 committer task4233 <29667656+task4233@users.noreply.github.com> 1620491725 +0900 feat: めもを追加 $ python -c 'import zlib; print zlib.decompress(open("objects/a5/b6b52f47aba96730ab61471ddcdff864e5dd8c").read())' | xxd -g 1 00000000: 74 72 65 65 20 31 30 38 00 31 30 30 36 34 34 20 tree 108.100644 00000010: 52 45 41 44 4d 45 2e 6d 64 00 16 29 08 35 a0 f7 README.md..).5.. 00000020: 4c cf 30 cb f3 0d 79 1c 84 39 2a 9d cc e6 31 30 L.0...y..9*...10 00000030: 30 36 34 34 20 66 6c 61 67 2e 74 78 74 00 4c bb 0644 flag.txt.L. 00000040: 03 5d 2f f0 72 12 7b 4e 22 91 94 85 12 7d 22 73 .]/.r.{N"....}"s 00000050: e8 8e 31 30 30 36 34 34 20 6e 6f 74 65 2e 6d 64 ..100644 note.md 00000060: 00 62 33 7f db 59 ce b0 48 f7 da 9e af 76 89 23 .b3..Y..H....v.# 00000070: d7 44 93 08 42 0a .D..B. $ python -c 'import zlib; print zlib.decompress(open("objects/4c/bb035d2ff072127b4e22919485127d2273e88e").read())' blob 40ctf4b{0verwr1te_1s_n0t_c0mplete_1n_G1t}
ctf4b{0verwr1te_1s_n0t_c0mplete_1n_G1t}
rewriter (pwnable)
$ ./chall [Addr] |[Value] ====================+=================== 0x00007ffe2f791a80 | 0x0000000000000000 <- buf 0x00007ffe2f791a88 | 0x0000000000000000 0x00007ffe2f791a90 | 0x0000000000000000 0x00007ffe2f791a98 | 0x0000000000000000 0x00007ffe2f791aa0 | 0x0000000000000000 <- target 0x00007ffe2f791aa8 | 0x0000000000000000 <- value 0x00007ffe2f791ab0 | 0x0000000000401520 <- saved rbp 0x00007ffe2f791ab8 | 0x00007f9a114a0bf7 <- saved ret addr 0x00007ffe2f791ac0 | 0x0000000000000001 0x00007ffe2f791ac8 | 0x00007ffe2f791b98 Where would you like to rewrite it?
実行すると、stackの情報が見える。ソースコードを見ると、win関数があり、フラグを表示させている。
$ readelf -s chall | grep win 67: 00000000004011f6 69 FUNC GLOBAL DEFAULT 15 win
ret addrをwin関数のアドレスに書き換えれば、フラグが表示される。
$ nc rewriter.quals.beginners.seccon.jp 4103 [Addr] |[Value] ====================+=================== 0x00007fffbb1a1530 | 0x0000000000000000 <- buf 0x00007fffbb1a1538 | 0x0000000000000000 0x00007fffbb1a1540 | 0x0000000000000000 0x00007fffbb1a1548 | 0x0000000000000000 0x00007fffbb1a1550 | 0x0000000000000000 <- target 0x00007fffbb1a1558 | 0x0000000000000000 <- value 0x00007fffbb1a1560 | 0x0000000000401520 <- saved rbp 0x00007fffbb1a1568 | 0x00007f942ab9ebf7 <- saved ret addr 0x00007fffbb1a1570 | 0x0000000000000001 0x00007fffbb1a1578 | 0x00007fffbb1a1648 Where would you like to rewrite it? > 0x00007fffbb1a1568 0x00007fffbb1a1568 = 0x00000000004011f6 [Addr] |[Value] ====================+=================== 0x00007fffbb1a1530 | 0x3030303030307830 <- buf 0x00007fffbb1a1538 | 0x3131303430303030 0x00007fffbb1a1540 | 0x00000000000a3666 0x00007fffbb1a1548 | 0x0000000000000000 0x00007fffbb1a1550 | 0x00000000004011f6 <- target 0x00007fffbb1a1558 | 0x00007fffbb1a1568 <- value 0x00007fffbb1a1560 | 0x0000000000401520 <- saved rbp 0x00007fffbb1a1568 | 0x00000000004011f6 <- saved ret addr 0x00007fffbb1a1570 | 0x0000000000000001 0x00007fffbb1a1578 | 0x00007fffbb1a1648 ctf4b{th3_r3turn_4ddr355_15_1n_th3_5t4ck}
ctf4b{th3_r3turn_4ddr355_15_1n_th3_5t4ck}
only_read (reversing)
Ghidraでデコンパイルする。
void main(void) { ssize_t sVar1; long in_FS_OFFSET; undefined8 local_28; undefined8 local_20; undefined4 local_18; undefined2 local_14; char local_12; long local_10; local_10 = *(long *)(in_FS_OFFSET + 0x28); local_28 = 0; local_20 = 0; local_18 = 0; local_14 = 0; local_12 = '\0'; sVar1 = read(0,&local_28,0x17); *(undefined *)((long)&local_28 + sVar1) = 0; if (((((((char)local_28 == 'c') && (local_28._1_1_ == 't')) && (local_28._2_1_ == 'f')) && (((local_28._3_1_ == '4' && (local_28._4_1_ == 'b')) && ((local_28._5_1_ == '{' && ((local_28._6_1_ == 'c' && (local_28._7_1_ == '0')))))))) && (((char)local_20 == 'n' && ((((((local_20._1_1_ == '5' && (local_20._2_1_ == 't')) && (local_20._3_1_ == '4')) && ((local_20._4_1_ == 'n' && (local_20._5_1_ == 't')))) && ((local_20._6_1_ == '_' && ((local_20._7_1_ == 'f' && ((char)local_18 == '0')))))) && (local_18._1_1_ == 'l')))))) && ((((local_18._2_1_ == 'd' && (local_18._3_1_ == '1')) && ((char)local_14 == 'n')) && ((local_14._1_1_ == 'g' && (local_12 == '}')))))) { puts("Correct"); } else { puts("Incorrect"); } if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) { /* WARNING: Subroutine does not return */ __stack_chk_fail(); } return; }
文字を比較している部分の比較文字を順に並べる。
ctf4b{c0n5t4nt_f0ld1ng}
children (reversing)
straceでPIDを答えていく。最後に子プロセスの数を答えたら、フラグが表示される。
$ strace ./children execve("./children", ["./children"], 0x7fffa79a50a0 /* 54 vars */) = 0 brk(NULL) = 0x5606fbe07000 access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory) access("/etc/ld.so.preload", R_OK) = -1 ENOENT (No such file or directory) openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3 fstat(3, {st_mode=S_IFREG|0644, st_size=124482, ...}) = 0 mmap(NULL, 124482, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f6511236000 close(3) = 0 access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory) openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3 read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\20\35\2\0\0\0\0\0"..., 832) = 832 fstat(3, {st_mode=S_IFREG|0755, st_size=2030928, ...}) = 0 mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f6511234000 mmap(NULL, 4131552, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7f6510c3b000 mprotect(0x7f6510e22000, 2097152, PROT_NONE) = 0 mmap(0x7f6511022000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1e7000) = 0x7f6511022000 mmap(0x7f6511028000, 15072, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7f6511028000 close(3) = 0 arch_prctl(ARCH_SET_FS, 0x7f6511235500) = 0 mprotect(0x7f6511022000, 16384, PROT_READ) = 0 mprotect(0x5606fa69e000, 4096, PROT_READ) = 0 mprotect(0x7f6511255000, 4096, PROT_READ) = 0 munmap(0x7f6511236000, 124482) = 0 fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 2), ...}) = 0 brk(NULL) = 0x5606fbe07000 brk(0x5606fbe28000) = 0x5606fbe28000 write(1, "I will generate 10 child process"..., 36I will generate 10 child processes. ) = 36 write(1, "They also might generate additio"..., 51They also might generate additional child process. ) = 51 write(1, "Please tell me each process id i"..., 58Please tell me each process id in order to identify them! ) = 58 write(1, "\n", 1 ) = 1 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79373 write(1, "Please give me my child pid!\n", 29Please give me my child pid! ) = 29 --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79373, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- fstat(0, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 2), ...}) = 0 read(0, 79373 "79373\n", 1024) = 6 write(1, "ok\n", 3ok ) = 3 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79374 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79375 --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79374, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- write(1, "Please give me my child pid!\n", 29) = ? ERESTARTSYS (To be restarted if SA_RESTART is set) --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79375, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- write(1, "Please give me my child pid!\n", 29Please give me my child pid! ) = 29 read(0, 79375 "79375\n", 1024) = 6 write(1, "ok\n", 3ok ) = 3 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79378 write(1, "Please give me my child pid!\n", 29Please give me my child pid! ) = 29 read(0, 0x5606fbe07670, 1024) = ? ERESTARTSYS (To be restarted if SA_RESTART is set) --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79378, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- read(0, 79378 "79378\n", 1024) = 6 write(1, "ok\n", 3ok ) = 3 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79379 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79380 --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79379, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79380, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- write(1, "Please give me my child pid!\n", 29Please give me my child pid! ) = 29 read(0, 79380 "79380\n", 1024) = 6 write(1, "ok\n", 3ok ) = 3 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79381 write(1, "Please give me my child pid!\n", 29Please give me my child pid! ) = 29 read(0, 0x5606fbe07670, 1024) = ? ERESTARTSYS (To be restarted if SA_RESTART is set) --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79381, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- read(0, 79381 "79381\n", 1024) = 6 write(1, "ok\n", 3ok ) = 3 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79384 write(1, "Please give me my child pid!\n", 29Please give me my child pid! ) = 29 --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79384, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- read(0, 79384 "79384\n", 1024) = 6 write(1, "ok\n", 3ok ) = 3 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79441 write(1, "Please give me my child pid!\n", 29Please give me my child pid! ) = 29 read(0, 0x5606fbe07670, 1024) = ? ERESTARTSYS (To be restarted if SA_RESTART is set) --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79441, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- read(0, 79441 "79441\n", 1024) = 6 write(1, "ok\n", 3ok ) = 3 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79443 write(1, "Please give me my child pid!\n", 29Please give me my child pid! ) = 29 read(0, 0x5606fbe07670, 1024) = ? ERESTARTSYS (To be restarted if SA_RESTART is set) --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79443, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- read(0, 79443 "79443\n", 1024) = 6 write(1, "ok\n", 3ok ) = 3 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79444 write(1, "Please give me my child pid!\n", 29Please give me my child pid! ) = 29 read(0, 0x5606fbe07670, 1024) = ? ERESTARTSYS (To be restarted if SA_RESTART is set) --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79444, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- read(0, 79444 "79444\n", 1024) = 6 write(1, "ok\n", 3ok ) = 3 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f65112357d0) = 79445 write(1, "Please give me my child pid!\n", 29Please give me my child pid! ) = 29 read(0, 0x5606fbe07670, 1024) = ? ERESTARTSYS (To be restarted if SA_RESTART is set) --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=79445, si_uid=1000, si_status=1, si_utime=0, si_stime=0} --- read(0, 79445 "79445\n", 1024) = 6 write(1, "ok\n", 3ok ) = 3 wait4(-1, NULL, 0, NULL) = 79373 write(1, "How many children were born?\n", 29How many children were born? ) = 29 read(0, 12 "12\n", 1024) = 3 write(1, "ctf4b{p0werfu1_tr4sing_t0015_15_"..., 40ctf4b{p0werfu1_tr4sing_t0015_15_usefu1} ) = 40 lseek(0, -1, SEEK_CUR) = -1 ESPIPE (Illegal seek) exit_group(0) = ? +++ exited with 0 +++
ctf4b{p0werfu1_tr4sing_t0015_15_usefu1}
be_angry (reversing)
正しい結果のルートを確認し、angrで解く。
import angr base = 0x400000 ok = [0x00002539] ng = [0x0000258d, 0x00001435, 0x00001378, 0x00001f78, 0x000026c4, 0x00001963, 0x00002031, 0x00001947, 0x00001eb4, 0x0000251d] for i in range(len(ok)): ok[i] = ok[i] + base for i in range(len(ng)): ng[i] = ng[i] + base p = angr.Project('./chall') state = p.factory.entry_state() sim = p.factory.simulation_manager(state) sim.explore(find=ok, avoid=ng) if len(sim.found) > 0: print(sim.found[0].posix.dumps(0))
ctf4b{3nc0d3_4r1thm3t1c}
osoba (web)
リンクされているページにアクセスすると、以下のURLに遷移する。
https://osoba.quals.beginners.seccon.jp/?page=public/wip.html
pageパラメータでページが指定できる。ディレクトリトラバーサルの問題のようだ。https://osoba.quals.beginners.seccon.jp/?page=../flagにアクセスしてみるとフラグが表示された。
ctf4b{omisoshiru_oishi_keredomo_tsukuruno_taihen}
cant_use_db (web)
$20,000しか持っていないが、$10,000のNoodleを2つ、$20,000のSoupを1つ購入する必要がある。プログラムを見ると、きちんとセッション管理されていないので、素早く、Noodles→Soup→Noodlesの順にBuyをクリックすれば購入できる。この後、Eatしたら、フラグが表示された。
ctf4b{r4m3n_15_4n_3553n714l_d15h_f0r_h4ck1n6}
simple_RSA (crypto)
eが小さいため、Low Public-Exponent Attackで復号する。
import gmpy from Crypto.Util.number import * with open('output.txt', 'r') as f: n = int(f.readline().rstrip().split(' = ')[1]) e = int(f.readline().rstrip().split(' = ')[1]) c = int(f.readline().rstrip().split(' = ')[1]) m = gmpy.root(c, e)[0] assert pow(m, e, n) == c flag = long_to_bytes(m) print flag
ctf4b{0,1,10,11...It's_so_annoying.___I'm_done}
Logical_SEESAW (crypto)
暗号処理の概要は以下の通り。
・flag: flagの2進数のlist ・key : flagと同じ長さの0, 1のリスト ・16回以下を繰り返す。 ・m = 0.5 ・flagの長さだけ以下を繰り返す。 ・n: 1以下のランダム ・nがmより大きい場合、各ビットでkeyとの&を結合したものを結合する。
16回の&の計算で"1"が1個でもある場合は"1"にし、それ以外は"0"にする。
from Crypto.Util.number import * with open('output.txt', 'r') as f: cipher = eval(f.read().split(' = ')[1]) bin_flag = '' for i in range(len(cipher[0])): found_1 = False for j in range(16): if cipher[j][i] == '1': found_1 = True break if found_1: bin_flag += '1' else: bin_flag += '0' flag = long_to_bytes(int(bin_flag, 2)) print flag
ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}
GFM (crypto)
enc = key * M * key → M = key.inverse() * enc * key.inverse()
この計算をすれば、フラグがわかる。
#!/usr/bin/sage p = 331941721759386740446055265418196301559 key = [ [116401981595413622233973439379928029316, 198484395131713718904460590157431383741, 210254590341158275155666088591861364763, 63363928577909853981431532626692827712, 85569529885869484584091358025414174710, 149985744539791485007500878301645174953, 257210132141810272397357205004383952828, 184416684170101286497942970370929735721], [42252147300048722312776731465252376713, 199389697784043521236349156255232274966, 310381139154247583447362894923363190365, 275829263070032604189578502497555966953, 292320824376999192958281274988868304895, 324921185626193898653263976562484937554, 22686717162639254526255826052697393472, 214359781769812072321753087702746129144], [211396100900282889480535670184972456058, 210886344415694355400093466459574370742, 186128182857385981551625460291114850318, 13624871690241067814493032554025486106, 255739890982289281987567847525614569368, 134368979399364142708704178059411420318, 277933069920652939075272826105665044075, 61427573037868265485473537350981407215], [282725280056297471271813862105110111601, 183133899330619127259299349651040866360, 275965964963191627114681536924910494932, 290264213613308908413657414549659883232, 140491946080825343356483570739103790896, 115945320124815235263392576250349309769, 240154953119196334314982419578825033800, 33183533431462037262108359622963646719], [53797381941014407784987148858765520206, 136359308345749561387923094784792612816, 26225195574024986849888325702082920826, 262047729451988373970843409716956598743, 170482654414447157611638420335396499834, 270894666257247100850080625998081047879, 91361079178051929124422796293638533509, 34320536938591553179352522156012709152], [266361407811039627958670918210300057324, 40603082064365173791090924799619398850, 253357188908081828561984991424432114534, 322939245175391203579369607678957356656, 63315415224740483660852444003806482951, 224451355249970249493628425010262408466, 80574507596932581147177946123110074284, 135660472191299636620089835364724566497], [147031054061160640084051220440591645233, 286143152686211719101923153591621514114, 330366815640573974797084150543488528130, 144943808947651161283902116225593922999, 205798118501774672701619077143286382731, 317326656225121941341827388220018201533, 14319175936916841467976601008623679266, 112709661623759566156255015500851204670], [306746575224464214911885995766809188593, 35156534122767743923667417474200538878, 35608800809152761271316580867239668942, 259728427797578488375863755690441758142, 29823482469997458858051644485250558639, 137507773879704381525141121774823729991, 29893063272339035080311541822496817623, 292327683738678589950939775184752636265] ] enc = [ [133156758362160693874249080602263044484, 293052519705504374237314478781574255411, 72149359944851514746901936133544542235, 56884023532130350649269153560305458687, 67693140194970657150958369664873936730, 227562364727203645742246559359263307899, 98490363636066788474326997841084979092, 323336812987530088571937131837711189774], [244725074927901230757605861090949184139, 63515536426726760809658259528128105864, 297175420762447340692787685976316634653, 279269959863745528135624660183844601533, 203893759503830977666718848163034645395, 163047775389856094351865609811169485260, 103694284536703795013187648629904551283, 322381436721457334707426033205713602738], [17450567396702585206498315474651164931, 105594468721844292976534833206893170749, 10757192948155933023940228740097574294, 132150825033376621961227714966632294973, 329990437240515073537637876706291805678, 57236499879418458740541896196911064438, 265417446675313880790999752931267955356, 73326674854571685938542290353559382428], [270340230065315856318168332917483593198, 217815152309418487303753027816544751231, 55738850736330060752843300854983855505, 236064119692146789532532278818003671413, 104963107909414684818161043267471013832, 234439803801976616706759524848279829319, 173296466130000392237506831379251781235, 34841816336429947760241770816424911200], [140341979141710030301381984850572416509, 248997512418753861458272855046627447638, 58382380514192982462591686716543036965, 188097853050327328682574670122723990784, 125356457137904871005571726686232857387, 55692122688357412528950240580072267902, 21322427002782861702906398261504812439, 97855599554699774346719832323235463339], [298368319184145017709393597751160602769, 311011298046021018241748692366798498529, 165888963658945943429480232453040964455, 240099237723525827201004876223575456211, 306939673050020405511805882694537774846, 7035607106089764511604627683661079229, 198278981512146990284619915272219052007, 255750707476361671578970680702422436637], [45315424384273600868106606292238082349, 22526147579041711876519945055798051695, 15778025992115319312591851693766890019, 318446611756066795522259881812628512448, 269954638404267367913546070681612869355, 205423708248276366495211174184786418791, 92563824983279921050396256326760929563, 209843107530597179583072730783030298674], [662653811932836620608984350667151180, 304181885849319274230319044357612000272, 280045476178732891877948766225904840517, 216340293591880460916317821948025035163, 79726526647684009633247003110463447210, 36010610538790393011235704307570914178, 284067290617158853279270464803256026349, 45816877317461535723616457939953776625] ] key = matrix(Zmod(p), key) enc = matrix(Zmod(p), enc) M = key.inverse() * enc * key.inverse() flag = '' end = False for i in range(8): for j in range(8): c = chr(M[i][j]) flag += c if flag[-1] == '}': end = True break if end: break print flag
ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}
Imaginary (crypto)
サーバの処理概要は以下の通り。
■1._save() ・re: Real part入力 ・im: Imaginary part入力 ・numbers['<re> + <im>i'] = [re, im] ■2._show() ・numbersの一覧を表示 ■3._import() ・data: 入力(hex文字列) ・enc: dataのhexデコード ・固定のkeyでencをAES-ECB復号 ・復号したデータをjsonとして読み込み ・numbersの一覧を表示 ■4._export() ・numbersのダンプ文字列をパディング→表示 ・AES-ECB暗号化→表示 ■5._secret() ・numbers一覧に1337iがあったら、フラグを表示
以下の状況を作り、暗号を入手したら、星印の暗号ブロックを取り出す。
0123456789abcdef
{"10000000000 + ★
1337i": [1000000★
0000, 1337], "1
+ 1i": [1, 1], "★
100 + 100i": [10
0, 100]}PPPPPPPP★取り出した暗号ブロックを以下の順に並べればよい。
0123456789abcdef
{"10000000000 +
+ 1i": [1, 1], "
1337i": [1000000
0, 100]}import socket def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('imaginary.quals.beginners.seccon.jp', 1337)) im_numbers = [(10000000000, 1337), (1, 1), (100, 100)] for im_num in im_numbers: data = recvuntil(s, '> ') print data + '1' s.sendall('1\n') re = str(im_num[0]) im = str(im_num[1]) data = recvuntil(s, '> ') print data + re s.sendall(re + '\n') data = recvuntil(s, '> ') print data + im s.sendall(im + '\n') data = recvuntil(s, '> ') print data + '4' s.sendall('4\n') data = recvuntil(s, '\n').rstrip() print data data = recvuntil(s, '\n').rstrip() print data data = recvuntil(s, '\n').rstrip() print data enc = data.decode('hex') print len(enc) new_enc = (enc[:16] + enc[48:64] + enc[16:32] + enc[80:]).encode('hex') data = recvuntil(s, '> ') print data + '3' s.sendall('3\n') data = recvuntil(s, '> ') print data + new_enc s.sendall(new_enc + '\n') data = recvuntil(s, '\n').rstrip() print data data = recvuntil(s, '-' * 50 + '\n').rstrip() print data data = recvuntil(s, '-' * 50 + '\n').rstrip() print data data = recvuntil(s, '> ') print data + '5' s.sendall('5\n') data = recvuntil(s, '\n').rstrip() print data data = recvuntil(s, '\n').rstrip() print data
実行結果は以下の通り。
Welcome to Secret IMAGINARY NUMBER Store!
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 10000000000
Imaginary part> 1337
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 1
Imaginary part> 1
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 100
Imaginary part> 100
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 4
{"10000000000 + 1337i": [10000000000, 1337], "1 + 1i": [1, 1], "100 + 100i": [100, 100]}
Exported:
e54884837e5c0ff5d78f65863c10af962a49fc4019c3b5747d3b8c655849bcd8b08f9fb9e87f357604d073668c66dc3979e462c995a4501631c7f1cdf8a1a2360d08e7159e40d7384a2f4c2690c78c21dae1dd7583814f94d85f26d5996c714e
96
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 3
Exported String> e54884837e5c0ff5d78f65863c10af9679e462c995a4501631c7f1cdf8a1a2362a49fc4019c3b5747d3b8c655849bcd8dae1dd7583814f94d85f26d5996c714e
Imported.
--------------------------------------------------
10000000000 + + 1i: (1, 1)
1337i: (10000000, 100)
--------------------------------------------------
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 5
Congratulations!
The flag is ctf4b{yeah_you_are_a_member_of_imaginary_number_club}
ctf4b{yeah_you_are_a_member_of_imaginary_number_club}
Field_trip (crypto)
ナップザック暗号。LLLを使って復号する。
from Crypto.Util.number import long_to_bytes def is_valid_vector(b): if b[0] != 0: return False for i, x in enumerate(b): if i != 0 and abs(x) != 1: return False return True pub_key = [1627727230910376679190305250495462377673127325457772051463473603239280851247844857775094804468541458382943793317239787693930638537905012556126829098198853, 11390077915029058809550131014512708496324218365383793403681859478983277851788559377973666759678894435638593981031042225181697704452107123180828946159773515, 8179148350749291474514716907983121255146115753248586194447416551426945499482207275600097490935543753034574160607266468264368850157525750760264486882342004, 10941812031082272057798702874172927467797501065302416966001023128384698906928085390135010716098940533908593173515390255250462556662539593195364174183111378, 3614745341275480428658319936106342479447545475997102535381861144548202616710068200734103360803941309632252623075660097928171614636575252144104941167875823, 823178354506932008674641402551278888372261897630495965386060191754392263016108442664620321118524856044971184623847186758394463971043188530296897451771186, 6126448477839481210946440528787637248330004648968502621267179732866433426925983876878526325407025084527441161833253484921016836135453814544622972372789122, 7466110955532217718350434679985113267727029661150471938943244057893689660733974538173921362412025690616586611377720710981300593198085731197422760123486823, 8494763827840222748734700648979436004399105472251068803766808893440611752185480154140145100605542790978072404829682982969121103538123360622748789468463235, 11189720630530432372988722422207131896593163626212669159020725119617893436033981396794415249303994853786917522131094575897127888600143225647812363683556711, 1715148450280854136862317182605666023423823213970399964487054641958918804151884265498646179998842243400236338074592006759506277918874694729594147582035223, 5540431799313225600289987101975658390666115836842131612473239501357335750526216599306611213275093940185339830230979569745307094862150569297375944630143685, 6065288708774786746551562482382919833260656987958350973874133802701002919726540869583838838759287884702711861900261459529790522631020994523440533144502775, 7234486161196695664277498569820928727263659579862329533231742765775361673322113762206501017047056413054134570841827024859772736445100885511621826030636721, 5790466157587780811391418203868871988082506102567632509545303269169653572768191738557448523974150628231236540920327049499163032154806889411357922070960923, 614487011969781591950160360975242589085019947676643049152128264494968822101147186721613098402364118730615692871650144954496839040414405067974702421023905, 2278335646833352836053675691559323543806718574568397090218657707516163081796224967487437830189535674711866517339720796812479305160299543957122930902733680, 134879407361379889128094711300170056598390106523526115878191161673136372971584663792937617159109985222609270062841930765578765868002121297161450924875670, 9519287056894525158582578864977452979099306021811340603346876269211863740542948640369599220180050455648379571390554225127442591697808606219706674595426234, 8402285089367247619745011222681496327228844899382581802919813910782074703470238610758895365966927878107041275900491204851884282695630780037206677089073743, 5406457121320262339650448405765205909738170940504528472739736687195948514104117332533865686024659827591710796087546713263642562769582609048315709994928120, 3801142902357168548686125964812533589729813463183268403565815227989154972362571932731819983704767934865803934241215040857671291683075724662922338415917182, 5436947858801618770870878269048974285422847359285195936610682423767931295811884290027916455982229786770673284249525164815726004308812462166914799567512132, 3815052792278989714677334168820537877167491234877274326563177152219263932218376863319752340985935154603585067421571719480783708315218297849199545235122158, 7027654996878753275961749122684655552094983534693747937102146760033187963841168663352245494579053154889790710851894666675012966264073470852357878798185461, 1902120513092875903338226046347919002820646057582844141644280347474263924997621676201569803130224359726311851288100274056706312976734099927488849060865100, 11761048354354487182165243290860187512062141561289470397986167013898235429358707127696368115069038004916028536939325487876797540965691324574012326619996716, 9757529573128395073155274559294819779368946395358435204233094762544296369601908201919613288263346489553542399982377228944641012976067072706476767936937491, 2453946098113482646488949231406349598804639726542182990917700647199960018577504360015030201773257233191736013580250768440614299316063045659162111320187018, 9319706037803173583171999553640056770008389931059980211073835507260771807765054342788152787019226685278576061693822692868824482538539619437423931723867638, 2415898081000285885317495095869472168214386057550401076099272996668473089357177847144038836740891535925645870811083042646884362664103196192764729813731836, 6831371739629516878762522327702302241691133397282458321594420516244457682248807904681947662649834044913983745000847132408435191823193733626430289939177704, 8911487453444536593323920821809421883218471526912139746762963559650262957593522887117811194390719914863010957953813489075136297325877225195754168400092143, 10827165969679594628739062220054978610293037445161650396571452340162805594515879042614168001849163738612474327713960410907001062746512950632119899645486165, 704502156006234895839438994186203068165985741674000184830486957231155986311282679180631398966930213171517941820858545126492495344870861094407012184640823, 4290415868027081329996593194887552166008805715995986555372686051077953073250496320908121226211705000105956461168744315858180066368242874040891532657113169, 10545064273500469407002351635866768900216078230158001025925896743623392315718385811101431137913336305418674086955813416589952935610377379991777656464560904, 222038761397496749360785916329206840697038382632411616626840724191778442228487034550449387870944140465498765132320783016190199911880849496664880021486811, 1441186128607304956019821803029517117342542746331149661877318328445155144327519269434552605831697245827929704875263722242762828396110183771144964459394537, 6262035322760676455872259557860354851246503548034172638052912261395035948982118234312601487324050800839022328905285373880135361896745345697099469992851131, 4524184613244291795109754414667150818999629856838115549409097166729848395081524481473123941545320222662731732155390386071843025802825179816381298820729824, 5283966263613790830455133450578806522976393376747821388280595897660468710659040194781402893846259456267710256514673635793738636888433235312976117540997670, 734269568748111640052090946231180906652495087236442702545338576377208172123085276589342632556585327179776362520321678519591781841790141214498484270905176, 9451656806863570616172924236279721588970386798009311529339115014539046020513297990270343561908720603044124605812085133334217197137400578937155121179082520, 3051642371650657054700521038491519744705758620980094104902981323717627057520029747610177450175370083995813698968822095618298179968058178062764130608659423, 7138952449752237733780319852689997148652360533005590188952403508900689828377062768778919668480243722079246374005954390574613559146429228635500313866647830, 338855726414699556488111033893516095818452279804805254966111715246104055445804382690731870669031649972111753917285671926417016391990572580298041758371253, 9434338110989485656020470689018936204735538469042920590064694759331237737230785701304245293791165210985574378910680725501788497370867036347820422455861008, 11743357680578349359162842808973807055764041927045206000202223764225228589230152100644412242832121778126080931892859490461297768718139167127509484426935516, 10809477666198375316415855765052746110763351926084144990851771467019653102707561871201368035835499988211685995329231458471783072292334735121148934257474481, 8361290012462548161951254835930186683493837370922544617362025529237532210142924359445724137459698924851513253914440872353889163895924265960022186220544709, 9110331121231523509307877539206254496672950206166437894520019335519961179869340990239003361109383043974388021961851540679419112950782472645836218947069184, 10393081243233784801735338636405290390807650076446916623218248492311682427662136868388090954521461644084639834083277464607638024855738147795387101337574226, 8635144191933378357854933636265474571012056586049858041465470568749464263500256261392037808005866345720862774122069273582266436367817433458956532049780774, 4418352683953086382401924269854964217677896486679104773071252777228873262401683489714714052284264053149769016874563276933086640659387489800484854697533082, 11405236243645314277535277368602821528967628188171456747788000113810218023475667423693365373226884179614448925519215120109302962469860586286886119774049347, 2771015879550163030165657530654451086641677020792616747235577420773494369048734442366451848062127222028674614372620701644053503582161481006114727140581880, 9898040106597885401583759646390295107361734996622402136464938780239784598493749472168979827154809586241421519720993011993090134889937532355080074694914236, 5777113427214185313997366187449136632797879082988812318910143048720548368905732814341066506919809935796023024351923191808765189492249761422655292085807672, 629078785533612849316912686429345503590958550796433801577651410881398124391524995844450352946049732397726053930432847836219823262977515490137563736301854, 10801401295641411092684548694395594070024865629243283117987852161404597651908799260812686233176670601757986605943575400167658544559357084608391881834446315, 230070532084711979714073115090944140276333108429708057888154566997156763934572283796043255414920534623439966012683795418379115522344166096620802666822158, 2653141234649791159270555987752178497577182383710867439287180210805265047951979750613536416122211396079337182535060893836409041761200653941413783366601647, 9819385030911488229711423422290746871860893626170080234281491318242107780563809621339193314159985954076683835744606911808745839075685015953738930366461504, 10787755099446585851067558577389646651361480328446469420228814545570006340103348743933813554961768885774075313271971611985063086273746596057549133130286996, 10263252536258338191094138495727374812304043040018874292736338983366473600613438579330512622405111321614329014124397343691422153751941094425939148115419144, 8264896351960310713538344637075442139532971304017521357074393238425679130058257615139742072920826381868768043200623504461528962772634922574219204008611446, 2147098598151809758012396937896797587780500058011635682566222787994691651248284456431917338694337594118487127099227127261521149212812046027401283431626653, 835919714553401942404334437551365593064566099647192274874446759913634276581629201627681467376279981880841428500989955273531853693899249169333824801078750, 3137791999402738811435798454665497017869650524841428289369351443750201278747862575707706000714058324362992205288888567315278677490077727774835379088436006, 1349083629045995316048152731789283957044698996027937078185713363080897115381735648010571340344037922487894330206612400451771128607496786215899669980572631, 7151470156920468764362424494490172229163475650617111710841057240618925425354832625922496799292567847545183967966217669595274609257135294729383362095738774, 969214900808450132888751546918076429566821040071276149919254643349125098280414720732281136532422094620745562927599642733412626063657268885891539827291347, 6837332378607129931141030022171984123309503518721395037825344337090610567350813310712435580992877616537619887480522470873869606202135747709672130000907665, 8364995496256554616029977590294874242060213310040785018239136897992699511676399955908119484626044885062103507697132148339409250907597810483796867399165984, 11150349307177473530307176249702818877580126605366046220776402492478240524483158185915502079277290319184145846124682470893997182480458282506949040910499392, 1658289696192983790897943272438520487042075314752724083703126291291970666851342327974958388331127028328164897980277317490557958037865872463479747423524926, 9131362533429004401441350892122360841764586109487383276247013461128740601257141642707756754491618871428100079351302334977304105019443858133126184771545043, 9330397298855941369542973735462725696662687125148526787140181659060684716824505001027119473890099274372275476966877359227102525263938755962082724482518050, 10253738743836159588621071259178219022563765128400530571588761301542176945143921956862350468019119752368079008322471485199577898502308114141549691485328119, 11600594703900902422866629561800220560103998368093720941938164737980026015168964844534647856810134441227007791139257922310172433764469537384240765031240277, 2244615925157610777383156726581397246130116260122731876532858274705570510773554286422504200282490618833439009494062776847822891629410146208293931139019598, 9733004403706149967520978404543771261324511435667728541178207212979721154676382281225409760729300022193360065470568452825325123972934958237623605165978375, 254354500603048544344274289207513537562120915759345747274593609495132631100017756321505502767286130589730909912096517138306900867943453650871702051139820, 8370794524988243638695092359570003691661556745490662742148202903860415924783217755602807126418561604959238898020252625472585689205979031497593592055937411, 8794340191988240556017659906713384748965043778452355164633928970799666465022803989063363371175889737930849051628085913544959957566363686438835153843412939, 5332480590532842430323558618578543509309546254138522597994235482505696944206135906595816348986471057105575982103534851867035705911825105890554636399117959, 3950651369214765379669331091209846132473398609747032844881769499832818398279627204457821432880778469543121042120812033753781942045800062715602362551437446, 8764597745555787966301901389786365105087694140863727334245233470132110641169237259387203997461935069288656230569502194991969216616783525833400312149135717, 10893671311442357810344005102450557175906931304022699347689646165105262580304776183017675980891676148589951193879822475240682617753093939204073908090934123, 9279851910251720350566986284138542667714345125643347097239195337905126099452241423018671935749811042002501428789486379723371928823690546158499167561377363, 7467311785687010437555773880658735452282769858571517461749051862992815684658577766003123130545826154620513903602757430481744043605817836120355235645161971, 5108725545796520008985875560900754734992617221769641586339788732236758184078757049778190729232684046606028473386534748941226434872542329986204159374865318, 11867699353985069790536624225866578465253057547038747367192323201103495572410886289392307344367210629571626846502738311475794548637804314691361883633660854, 3307955753584481516914855590837996820524452980430232447056686239509247300748140903481811349702734702088092190468590865868219632872299773637242697461456553, 10198102385245501857792898248520943901262126311232584209734399129163853603686024999279049967928201510400871689285418724239616764378384016527780204413216674, 8228299095729026478677409017032361626919004386605335618535716218424202290478453122140182082896822897053196677144530584164608155945616171423914566350006168, 5112786368092391279903606929743330066336471986263730056133931970470350367734928619591357871627106533582770983308703750603891628446704447489958729107713715, 10469735493230359064821542968197039289870670760006858877107911033538981312661996508702709711101453750156345711233887576764596618880116679535070758686367835, 9196198524335526563875694798089709262412006598320807967509365313289345737999012223767852725432769548784378062829358869705294718633979410353031005678221802, 6683277380933096532362852252484564886247729619973370408526339212096381484171620318859617374568197001310631889191807697663323642106913958849690224925461694, 9529613981769374073447341366884871937833846177760706872163980387662932372533823749575103833419092123484129940660046036074238463645988110467224610841798396, 2266794669069907087687293539109983357111262788594707965340396512153714241039180932421689734859164235712168843370543545431747673801363827867496870372125336, 1866657295458158454881522810715564591136349581564835527057025586296173873670918151349885379247546649061814138440749434231115994040006915887222214832216793, 9148338051604628974249176335472004157326441570701111334833644249222513670344916886670861683334321358810579899657217206257613558265823876085505454588007968, 3150970195117521652874271187992011688081846017889819628953971423349119288736936005559152214262722455740251518841347209225787560336272283302792820677155456, 2654815978280349195745421700490321540189264095484815485625765415487938591288435811537239820689235000000161324407221020096227903798822533164408384845279219, 10613712470437968081140979473098189731268139640670987306626304368616232817231479865616941989006606100283262512680880271451166161316286745812304949833618532, 584771700542193176410575206781719730381455972184594687314858310873745548037581699189913439808225843016877940196620523275735084018626160581660280994642977, 7752227206782612731330946605694126516789657852557775310044628700046190614760547318085553165126745983752673912673179603938501945102414356429679923126279635, 6181114125680462568335637321427121237211288385454147219539532450576260468665546332121469615286892296528834796051391696892578291511969538036639317451275393, 9135050673473900291782130971149267435204316475664597051965244543275596770270798810469766060093645817494350474433396115526366874458378951375630266775342673, 10823484837094701160540558686227927842943057819522139544135134044387262556730658594806349353577086449873005218586065819838718307881055159834974985844681301, 9983072533960933746418223838369711407232082297937881132317170649759456192810500555555337035974971942717934370671547654549936811199706777826630199849997893, 9496860292179603670920445704807780801671759827403400028732735007396868161785125605066594722355616018953537321578676302542059539384517799908274423326672419, 1703385660623950359050969801655519572699157230875334655419427425211519057467450009673619270811656302454948012601207060423808873812556848095400818203864, 1124824934298417769296957031482302153675496794359839176778073940948277366770010987547411988487713939288525606195470668176368430409031376391243742928188737, 3229481917557768819829086515377643522962590749891024608854142700316113763497423916549064184792610168714433142930480984048981188717417434429561511671863340, 8294104032436327777486159971264402767334649287841961190030297139466131416369517365641129837491598616986084921647405266807970727164692073754656655602529261, 10841558702848626512201447043784390704658214933053467482697472164169627348933072901533434861934797167954203691251466593055982136720490185778511573725463091, 3178930784687138843088596584997903179579922587867410882667347234930875487458734591193687966659517370268916417823125671401884196339836390571169682168714634, 7454151195962571505291413229201537150280824884428852910895643182678249719784935336643779191181482778848818993208221255258132534583411781119205078130090493, 2015156865486836120778682378960560170098671955237858754748152131638573845290736893280308181218687853014604174145816633360273506979314685066746558185772213, 7518280147605752377356085467400615547824826179564770315069235526007505409683817948956679988243512932507522237221929606038316891387806953147114552195723037, 2024819075929565623167333132137655283846300903116425428839619347379614001726638635657985601976090872185635173118822397894048579095835679930797308966510161, 6215993704628241793832033783162789293924516338030608992171516163123272062860326445636293235015378684705933988212973591046212191958652259015996841348525233, 10721074643733864954970318017687419861549782195881708432332255884413370619291750997381857646366632973722794738669419561902209255528214363399300572318598976, 11051099778413936201588813479333950625696456591449077944829525186174150306810041964709311295480133149976157065280899311313708649194744567649855692630214364, 1688310516465382129824706766300320323086828782213510237597315430363470883127564821837914550530086658434882374985922949368294443247364921794573340486906238, 3192364479471168028710837283899918625935362325330335301033556406770563105461096419504116373286876626652315031493543268384008485267512339959435053933841313, 10572194847482440812332986591051630462883201860708366563698662854481883222498284684687782612499400666528966898408853346133591660937905688329633621416854553, 3947736123018809396047345259826555348314283757126565484195977099646537310353904000152697460719528310696082204835098702895122864267256319395558913520116392, 11182766638391936877995854197520085129151384977709217790829422656082419193097932980148237939707803168327610358370853571892812158944282257498680855767229677, 3785005419673190260210131419611296437580991153996528806706953071932484677468263744891384933085989064774778069519276028906778427000799962507340099134917935, 5080917081750594708323405365145453207238012111759111382500875071859284459953169985334929889554817530710648209427731938198054042780871188922340543142924939, 4048618658491596677603187303911377706030641697591465631347400097836527581077675625158162761353955215178164330226108795767011183973412955473474219799087197, 10756640002316419897851435267941668380681904604159814743578516612294764433749019434802471420890142162949979364053015555721098798895592890837753394402601600, 9576566069431525883762715341983732560085629671089897559307942342017237423144442133049657728319197511124149519512976698322385517896297503762943044451831682, 7165568955290222509156785556616132982441722968221047749287853532522706162989495783845174854505888062434423314563689608447591958198763443599582520354403262, 4886305788841254495561906932817366567996456189096683440102055315067086182866905742486434971809212556403255604320990070575999450589283865669827032247378026, 7974570179507384046793957867326714371457957470114044411785079610018843160599140562038134667373750144719208045822373607909523650049764790454624533560094438, 4699399884541021847518656224539601167184097708756378716924596672912033629859806682769146527434005646171138846377909985611374237928982199839841484034595124, 284699436285137586151623117958887854384067390251467180741921703094848380911015079304006363413374407709029807303242873481239873129968266824381074061576781, 7424603511991768566970306812540965037304046015506639020124822754523996481221874622779988256386434795599778401964853467233299073228923733026307559753461753, 10204802163769309817146573619091345092885022518990654924014656950712859972992223551924164346235264566717972681978724897809251721761375877244325753782176857, 9438420831957673445603305728093735430853841298036258989011836327310515846466591187953907621823894906525289199249629125784422458200828675239244266235272346, 10890020912636917421687599720986965506018026168566001306712363618691959621006154914816267736938077225993112076739368505752571167457735320815453253378863503, 7612905558494937122786907665601018921881673472453283960241071713931932464659066013897727134859798086411171769879216045995689241333798042462244230212212984, 6550836530141701911622212575637172610040961303781916329326618809093764882252631974098246519703546676024381344519501504247292099463026478299004729842120794, 810463246670448806288456723577253991309434245269230870268065162161683791423034382984779736398143238385314386270683813736785640795616980760740211633626680, 7987182793636123387405676060009070849539867837366546908532424481956731048800366776798314558709408103425915728898034756937642304986810890072970609409560920, 7214351975158893076759227293921988348242566545977916782340607663706728189002123227844454484007467068046595059915519900187040379326564702309329878614144193, 11014878924638095287994257524709668434779725530794695530401129023156413550436897097358726050238680106826431375584530778605250124880702844280402008225394872, 6027887507568715893917001583622263960984925990340905403518345783740595181396031310602841240588909634580493242079149694551634238251017289222201905339455410, 416347896819517370094008870355298145260975680342177838528189406107683995143464927834127034596304824694484130253280370972827705469927428341950098126774907, 11163457967473117384909170091800080756098465652817504823829957246101519582406623920562879665741186067843806160145308672039236647314452825448974599553726514, 9053783100187331404171412931836385824515184111948767809413867380276679820649936390889334178130847227206809033839795986237398002538596094506862090790079370, 9819981805416004420939228090848428270273275315135728420672592580587456849727183520386676637280961225785470170028563422457684520710033836815957352641076656, 9099422152831608846445523884690686488729801810193179742928892208927495088869678721490572756945304623223593124143301850937075818103925239158419916092455832, 4423577950698286460626059676874777666863173105923291070406075608137350484265775306538076488967427903876263455370640828955831433683427915837489787681571104, 8756602113276572584327515563541785021885156596606825926384196017746588797560380054132379478133281808160622488923734499010823093056004931483459821079878584, 333126719900068218649984650898276581721876314324829547579365535415969541796750123020026055084245123391225191139147600319762747033880097952001528586613619, 7369702367521762727060275952126910129673008169982509956632808176742772738596846920777046904811187475688291150543995266534651134952974656031439986139640279, 2082799199108465498916580083784704029374798612211554268896160342266763106031569342542856087063877321514991732991254030062209651901743851475358154981091336, 8372258715871921984711084318371475306529362956110229335731717773030170640559593876258151246392797433258993127356247484151533876227372092507704978818762299, 11363939608613542162316118345022960798510877466323811731267325707620939632567030190215087390814765739175622571243027333413495842968402118709843171345209057, 3369719356483561545444940792209404189671394809909673685150113895593885526741601117980579861293222360031506015395948410107943057618465847851857629017021337, 3891507040973395370891557095282687378471080702589144672203318739556917713281013957214254764662956395750402238983505175330658129247692117209748428646988979, 4841437298113170733673811622315491999860260018197250450712753745063206624775276093082643398955242651840094676440631824725064149754775763109535437072598329, 5285163136257383594317771821481380172518348255388334236768828515368456565257150986678782783096670986106218219974638745661030434504183981097992990683389834, 7244116929896986409152403472296524576447775663505970094108789986102399989798939651538136211134583253147368128866311176849015387662060018429204373203882917, 7148506525887590405588915139400704234523641207593915972629337111053532230604043569291551513966362985886466513012302064587708085238549323074532238261929105, 9963569892216434098358658807251534860655159021141499917379945920250313978770919657650973084221026686207963270148354989236871921037008125320635811012429562, 4083231038473288903981795364527141098698470950916969669140777386661810905824053818094335667187521576982089894722121785936689098719720641047141775887885619, 2783788314467957767626366294911171310778689255399742535622249802506963607071489599250401846151948395505808426552847045942384003413532965612237381621803281, 9480491617103309579842630556508755350939077789372196051463181228494854894713982210404024973543443376963252760676054552352172548702910903277458343177156566, 3635429364237267158097629083423075371334216134912102395399443587668365674217468957824903594013330904699195406402865693233751839584364352027341368755854935, 10512981667787343474434123766399499997477931436681258061313671140829123476643229877218327020307534330562667672313170203756349669502382157014339683250964247, 9523260882926982368319161046924327498415945065442619931245103165210783676690576930491155298561540325169832005257298960723638671214008183533978109799943226, 8821529840762200230987342601372713314571576667046848202753835140978481743059025729341547664906327089784889179309805528352373783300015409440694498526802453, 3889011833429464584665382058129163296830025770986703817534403311481298622682949913268185847076341119959231106603819499559066684839808723190986345797294730, 6297833894994750508332367344339230109576795350737018003925458747380227258991762309042244773127464626474655334235127595180446112677686417583728900997000407, 1760580993763018538952442776136678506892159758376177668343574661932032517138571264664041285910343183567929592789229684581190582868840885043494028059145548, 1878349075050149698900567649931858097059976052165743708683218061733003305198473269136227375120889463183154947939758601333339524877223521121998759362189694, 1153881028955172548796413995891509447158808154001092914831702555572321224472153757269063442351457270745992276168611327881189379302990513606066403785037397, 1354358223850339886669589906081771646741444582933245990266741503788401468880301111475162932826849753299053269048808168611803883992487116859632452934337117, 2543377884923981424206502982559952756662944312446884306172193873371281396271026877421637622091903368826348654608641732603862340627036661889590442947531927, 11180070331634863421659326942954695855354411135806527591627639434182163636572574833713806184536037752699260808146541362264028865594295761466526576972822841, 1876044157639270095152731171181080065397794949339134253513517014818122966068827775030685216937939154007734964960492393433966781954313208696759345941096572, 10371430099994185472204699548408748044905813408067850241238238375805107275941350946511274188710313819596480556092765947208731899524618164738003278717300827, 11062773114779865261456167102313685917798343978846196446106343403832714394829785645472593554347810116685987941912922522999627132764032557020449831422203646, 10054072863070251371743882375307803093121932615191109140649824301459981488908599582245204018730319415235637278900632334082353686886849433443418405120003345, 11899130436532794506852251375418519516682965538478411626134165694080477666467891621837514385290629527954317340066073791969068384836623478676900518078492144, 3800279300556347862463102798984354928617374220518396876660726722145475720924549768399286700699390419995192400567218086102399360340221316874256916817269786, 1454947148349065856463673503402856502963580434612167600249860095631651888047663819039861980434456089663660230397115050479224033897345798648510977653561999, 2042470330662475573678989377098661429766022525672425312136276901388618218130280731245706624788119897930174958967595406027605059992960882778388524742722706, 1234466316196775376839414369545576872418957414559143172775038206383525000927730516952675718815486990989447248421995842318819533894488233801079449620739194, 9271029179787872970578591499796305060434913207434694840381590014888853464622436665409168097643583816031775853388603609072558269628091676020362129748533199, 4774006049363181543707013424043619624722110752475263766809952707315716132555412365539258234954892899737076119368604420130439903122534513533911949833743235, 623110557039911730730761834817043413841225662260405544713333348288325346206246696815306384870033925067051567408116233686600986656157873843902741673267719, 2069564772459439803719938786548180498693262686543372238863965419552080267984035520909550576789640672747255124939459370750757373319167495387965403174747875, 7009930087547627207463341159618322389574790808227199206178856629902591585272159790554326172427287447472376543486549214941749592725452858178087430338966770, 1949579642601550445176938316267401962008340575271606619055456197313569922910186952978532646082714333411065815595963623697989602613867680323849962329445328, 11473102336200916747844954216116155097772201756920091057358990979985199603080222884336057264448248212309791104537148189404198070915699582464690841703029405, 1149619512535738601211196767922880108257082979896142736945084581216263253245359015735818442104694183806457438676420946219043390360617857622541114743356625, 2728451593413071164353755775705571417160504975979542074503589190184105228575509775437861194810114128293804518550015503478674215376973558551801959937646423, 7348551730526134269844474344843320874593220152077150721293689908105376303123526293549457485523388054871559487100009886469120877549640875229125679910062900, 3980652757335090376997966895588998245582192975449382011909532268728853465365643067981211212812543763607316362585146788052930930128811388536930969342059979, 6027435835414897879227982281610804883898257447430395373655482693982905460207165696577025993816548891414301115457107032212880895723138070720653764226458649, 4935176743833633453254610852208777179108847720614483842026980697614902097198030677572108382421721697955784940692357115100326157600867058374344306754345335, 11380188380193543686552603209635990889129830058847840211484047666443921358239983121578443798338622961931123079081312386043081771886474890372630867350934523, 302987216748498327772215483663698180358086916475422751109337904686429747813576273027596185544180584711869887380062832681724092251772710838738355782182450, 811143629811997853354681978704899746490333224184384674857937414780703218886854529258709525197480284388948037380964255401025910568649894324446856632636592, 1912197174748050506709090151289853815332962565872780585712134602155119195678387971652769864474405775662028797382605103443081542911360430369860062463563893, 7291021864361814150510118731044864385204363543462889467753348110602838791870962501076106462997795429050059428094480878740697465713025274178808092567542212, 10470454741786470619594017615965958273332950307267197723934552764686005671405407576286379932688897606971338908824726882615845921705580372546409941175331037, 10181553581483434681781949968008741740061264764289389453230798650897899608022705896680919782100794147183000150901376195723151791411050033951290283786019977, 4258448968850182298881050787339455844058983218447958438955469542872009797484665292406639737321421521390721898187715427947024660792416519473288140642795272, 665126950818270052200683167429361468415424104577516367369570410295667254789977695909839338561441230603199269238113935924286711971526139364836371465706219, 5778603245576121661625744968094217982871142011195728227336698796177623583983932093421170892589521281377735094971545437150524492567792401307382096969659571, 9041169568361270824631079916805143667485107440403819673118982324331196605243710736252243694585470054722017092703832685314107118663876738553603881090379765, 8431011838980342769799616288411243768347548689119233157208349141492002200386542305507576767212556262869263553150643023836392407323405139253427329269366753, 8553706268926206579355730973791660092353863784751509372422644440790878753983928717623545538807559356829947772453965617876985508934310354104621043687587875, 6085701268163349706176631571460435367494457139886003603182612764217346443544862940087286859921717077555924920693652181971614741028158787295175507903805498, 8258027474231127629757419236092115748878321896277358390666269357460217304432166604893188156062734768320200621455881016473474077406349529408491337579070619, 217331193100935107368229358299722097535960890408924136554062054994468178500442930497503537444463416350072629320109394984373121597844999496670174734623901, 2615530940468368976430415020232745908496491487732778845358342691984855337966644151086347954705207248347432846086811344429509626971772151674138828479034407, 9960118652490492442626264557722940366236550945756405929154467678797068007119691196073161215135625171292061966393931591117075379707418718493207613281734128, 11883479956336240751620508565956647791575906464658043904847102787653384413540737438954113122506827116919889512801006983398795266218225358709015970474796209, 6152285147387893134308305627413716697035724893956326980324894196703036047676192332607132054448632203410660151536148743152836146945863580679445515576633313, 3087204177300702725903801544645938527062384514542059207838072215532344688679150676602943592074143292505943525492596313110869017003113441178426953737136320, 3757237385014563017951360020497685657808716037369726973798008159647192565347911506203832144238975399303316833405799994094392890515318875781045298318308651, 4174290778215893394677957264252893474678237242610027055294712957192373957647857206677916027186240373718927301908828095938016364127818908516883960408679053, 3748803300372512770866385104654922154470904205965026771319291886728164245927197518590781953321238268806575463481225816414707349949847056384636893007457721, 8034791604871081754393742620809047036249538255482307958153762277184366357510690505406748023739482129037447179804389566282826743874110772660769989993214140, 3647010606069854412551850026099222166287473701386238939796403152511252931742239857496752497988938568540423402614995772990646648482450299155961694607003150, 7806003716386838238944347755133023427857127411524200971653891977428639559902033732325074590574245675288515664031976582135757036821962959301244591185185836, 562123165970750916018523521274665280554207579150705704505991893938951905226252420500731924279293805682202106917135997949779952378356926548090996464183261, 10017225347599062251185778825601433952376955965940785104804810153710575101527601556073680944735221687545673318069762612385520657594749285103779943556203859, 11034121495368102793824149104460238045159050590264281508159716286752391769866225931653206949515929308837443453281068270892449202454489663082251103597579414, 1393756984740491625980042801423925923652694124513215825983448770637319821986725266222696274322782094225350417979883496797845297892870351570641796736429365, 3894233430764171021978166251097684223603711526228678617083090942307219791681305224470393733859806270321706191768448575635613494955972821171942019155576022, 5038527951098793046808059643802686028797058725403977118364390586086699770072322326201266880837915838731709376700104758344376656110092506598359671395752201, 9060876869828818448898852928359252910511417178029126609685283138824053964178895354434001568085161220224819591618740459295638904077934235248948941835465621, 1213284553098562533791961352335340028855774866108118873722749495214290050781676187996449060540282711962596299780371703456279525985966066640468482695387037, 9458104547506301061680450860449196327062010922531182109678643885802054328886528832025671540545677869267828858508683156236410816570296275103437238768105346, 10040054309381342148323598117554716384177326501952268974305486266186254782754797649740498654297024089530806441993039549600316509292085634401892126157777725, 2276927462611754797775080537543333252522721301228205773464099348201834053373985987075600025798802656981615274790492592630699705223288330490059041063861371, 11556387618265616484447806363024761014562917993396940861921977454240032115257066203918497109784248023494996743861411413922697151976403744004551897333587419, 9889259553854405678741508034426455964451772337345174356626295292298205602394952451135449468310970347202594428138122580204423010430923553611754754581066813, 7868119367862772149704911491499473892301419246641480987785226518125812257513053330287476237691301677750429689882087996945744571488509040895507410804183873, 11508002714196611606395235648239725836815494703321432338230737422973329400113158960696048138066722457604799065695576108785835121800314850011501948179743038, 10619053976801844838774915437764267913028709258001605358060442557707903258319114013374183185245387748828857617374056519624892149856249176171314055188176610, 201114180079927977316442203939901331713590891511639359168566794984727753167419382266922071288806881033628450144449718352186865225718313149653818834069046, 2190019323352646788039891107369737594638195699052572482340522786006963164742529768845844542244804881489436879523607337606022137474264008443779753796524324, 8994078524243073711186983175744445990617668670221279088217344780392324816856868718135841406968011026331111428134944981275543409823808438028673340180600361, 6533284532224150900776455616895133851200922713727543406843945334153660021579927964092546898761699064888593901931845363003227384361960946837683468780536186, 2900049820355985276596651350970201641910754953548208005611546296295010850954727597768565027123529585734943900449339351229077414389982399805851238537614728, 1005880173354315818215910490344169033790331192510294503391908220666556408162907870924876819721045548763740285934029434904116009033147300587812755020644144, 4429054545144565886236734238945768223549483534284407724097387393750175064863874353898699526770177337528927941471007913087408339512025427531471222352188598, 1285938780473331065877152772696342220861565553509736020905508189616388274844286113355903326372890919435684927488271321733483666403913781504709399179873478, 4159150342515004345261144815031223818657482125521340153877247384204372764658422497390807502845508068305611676258953299381534589394265725368949773437475664, 6576053057257377078820906137528289451395389785096859241738114487306122040955968123160457777083015623663591073050698149441279744926252972821085393074005333, 1378738974519907914149249225442590530115602428508531939708952252356105515635440550944988163800986109078848963934554394890364246215667532562795230121599389, 7530997786399165063460850133858426260366809458237917996971974273555406375229986518119701973615401731228222820028200964035186619721317616016026502478833825, 11371420348305380659910667615045099750167009510608284140696036190712641050353322760033584623633845930207049409269889108127939128060387804390620146397391005, 1406722966782959654726752002298837227734989674210304975712947321382221136256184622554373120305519551329471835182546103526035414290130221817761536912957815, 5758051768032037692984394788957178321113409313718798728174793963781211431894591306550233406904077870173730087305011890560525061122641038861810843224356132, 8375592464786617292066912032437580000072737070264996613521303068301506481293691262141521386631735548118808483692010811823373696054502206285565746271896624, 9625907624488495507256482396243781284122158414224512296964826016170998792851176860574572431609386683318175698871706280650379052753758050216492793527676711, 6077121672943640395277987812076880734154021482921918507769764026301498404990781416398855464804098928307277904801175596028922879606596629086997501055486057, 10938317339216777969309005338771442572315779569919804097449082853678275737846462681571834649938887549054815344340466436822987440964989371612298886307178807, 10266683373756264194186447415036327152615834323531488817490014686098650065547689251785469369732777946066207328196236032745636606950149996263882005409859068, 8427162246188488278348961620437187641769838216136551139544284534863388602834144470655144389658677000026573199236022413391175268573166429748835445411482658, 5717464833792973913319562092059026311110221447664287634460947091552289507231429020487445388817891744834227397036749333830249281129481189357590616693269535, 6388818019678030249042408529039004378409245276686402664154657767440109416203769306619383018656924981215056511384850552069151122129846170533781262522748912, 8058907696340647071107754590699635637331185362322234472755551469964443477794313636568312465633167061469262463754899612550256454461142900371675688057900157, 2650747991231745389958958911304551569853139256346350929307683312550450872545634238374819072544315331311085466011529241531384249952089342273098825176365572, 1795582396480470137527176284050645710132884527117486543781042591101197373917145734791679886383698097545356710330294515054344795103981124797423720912065788, 3052494597227398062986766578785396078205343919129668957958403133104993465160270251274373731365131485657799744057254790666584712327793616306716481909813582, 10125274627175346533926610345531381215155487891981319401506773913530942967488666544216346832250066513931463806744742351603339791989023259173734707387511997, 4905680337396302183882293200926552057123452464915594706482473859546742047185066973667304120028692253252104621914547092876701216499304788257812361954677824, 6788406585087459374008868766038523502662818879678483645630850915173078456811145138541048171988301388863438344097400187657040868535924005858978037488288657, 7987535346230340897650689272410982431583013895248851443363614799158842046321593827278953603690586270590653576153599776704899221489125881490179734913546180, 8668917726517583777868824898842831799933140622366155997499295528164949892618224804058794268889856672657589162182942581708183617533722037397902258002530895, 9655881640658079998109185276195348247028848976437592393891872239361101495373466311759967129786284249009503363294866452781555176175074514406596570855032885, 2243254436239103264649148279923978439297113563084946410869285186376198427685827681488062426734892419878174177945847856801922284074524600494618385520306773, 1370395445224087129252981159080973354642721975377684037523867648255769044694663959614655088192001525836838035825117690852844390101675187401512396538329654, 4656356018264588713126970771096540938860534429248562594457229986461965010462394518948976087164472484086375527533066794826178852068228773967304732965776642, 399595104452867236939487452774442870382730185220898620972098982860940846257358797206676225999483077781771650287888749325035861259261575979039839692262492, 6713094317103593591035416401288016658374527895040216154450781797709219652499792405003768632192355326331160459215694094704931391013755418496926953624700285, 1355018836283025742708846544067619719808654650957172598457945625126225415187893386450296522915846040605946952638451856428941453174991662324580099164411759, 8507312388193815039448605936770163526583300978792064893979853487224838987061551285368575763268148426788906220831176609730056029700392843807931184213757186, 2390915763452094063824684068272365759171848406604147217738985384144180505204991956237689281338506240218745984753955055494680218520622041831641785650384604, 5078775779350968152334228179925283860790974436015640731121894535584508877508449803458104048591112435333313257450614663322502851401769525184404429846816662, 1425564122989501182786990586943993793473032764333069827246235450438848390559886137108308116686220076822910325740852447268122991165884941809370496785162762, 3241557185717009458583866491496790535555873425192682369967408484532454523143616622825602173631183439057048896614677331862355583135778598344467632239621265, 11153886486498005363601960922463467341760192139357482824612504299845068740009509797094949564531439906328941599335110459532334944225340180499338091922473414, 4750339554868896196047869851866222454424215998958859589162250220636186354219417775182461279765710413851720284554693629603182622333067705806099109845670979, 3931689678588961771487503092252686799044554895341999274823183685441609027829749616204909660105256179107533811726668939651921392965108014523612326438454763, 11187638131483583043295930937674327604068710567565996413543552914014991119808667664531916767958198065684486668485361079752275150252491497563209373369489026, 7951154730710536892216170200330921561976344676074745084927394513732709335427919379562575393123463516219422246176438982950570737516171571233794420196666886, 1672105185912794004124818038268311924305321636283766784591904708276129195324814049081791432685559117731983780119720703133146952521104542489075767958624517, 5961298351722930109958690694504209488357119642165137305859737050609557432218480991926525556188466406512020308464626017185419266848018117342271389200068990, 2614791092577719712081127427916398870473955060880008274836166534656201118982263931935400058828969825633552149733933209355913619475322640831081073991096019, 7585989640990063110599210948433357802190782090362288612653066977287873913659636348347931158157250612988653924395845263983389111801086659635847485205155792, 4431808088762149440258933713632651937723965113354466368892895978425300447231680836376644074059558059224711681073893610493216931561336057461872809335815419, 7803424065303659891769090326828845084396802995889011459387130902032712116540019926662218626165288561308869447406929573895286984344209221478683590810037836, 11333465632518722706044944069452368469429296564009722650087924377614457953420253199332209735022605809814036297664863446336960387614479076573269329031750987, 9015046896873406255435786931788379566338694649982989302643634589663708173842716795343443511577662905506449004999936754531825070165614729532129356052128575, 11605497784351360234525700004313542522479606465344927573861628615111353117631482629714381940820675064966051516229437449884465509791106407640656382300239363, 3618112506546716532317705417297714426926133719388251635042604657890418824749256430743547870156065078623067964196242241099881802766943775618184489388984614, 2961952780271618644341511265207741924062876582075139491069703688326317506273106501877576791814338926919371801113717337612487657355874282727562430403186215, 1959860827301876193534452473130565833580576931994622570402458534809572211163546248253809832512083364950948854715506995993724605349255618000388575898620819, 9522502213326349795872611375564340926065360170250620972307193996920225151270140085190219961878238320516211124175040938476084033356336641564459714925394556, 6822893241651652944802867129943790227179941374865599671130155956732332020891862363512840518812230889010452540282244203720602490116223523996809092557679690, 6857422579671283864309505737866570751014092920497487113429028085441724197811232340915656160313885768238889308579776669697849014732800696848033650297379889, 4018143097421566596818458699109838662675933060812340723092984957628021473520663072311941893877060261979047503976803401869798199151609532367574647600368003, 6194607058501590733164566924844005093710661715500276174295952934514177124661068706559499237499314609830082367219229089919247640185368549101514384767175538] cipher = 1010137180395931262752398681857488526009620802401167859543237801022630704004744078316133982172587856565491470015404484864890095896964409269987597733836611756 matrix_size = len(pub_key) + 1 m_list = [ [0 for _ in range(matrix_size)] for _ in range(matrix_size) ] for i in range(matrix_size - 1): m_list[i][0] = pub_key[i] m_list[i][i+1] = 2 m_list[matrix_size - 1][i+1] = -1 flag = '' m_list[matrix_size - 1][0] = -cipher llled = Matrix(ZZ, m_list).LLL() flag_vecs = [] for basis in llled: if is_valid_vector(basis): flag_vecs.append(basis) for v in flag_vecs: m = '' for _bit in reversed(v[1:]): c = ("1" if _bit == 1 else "0") m = c + m flag += long_to_bytes(int(m, 2)) print flag
ctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}
