Backdoor CTF 2023¶
PRSA¶
from sage.all import *
from Crypto.Util.number import bytes_to_long, getPrime
import random
import time
random.seed(time.time())
message = b'flag{REDACTED}' ## the flag has been removed
F.<x> = PolynomialRing(GF(2), x)
p, q = [F.irreducible_element(random.randint(2 ** 10, 2 ** 12)) for _ in range(2)]
R.<y> = F.quotient_ring(p * q)
n = sum(int(bit) * y ** (len(bin(bytes_to_long(message))[2:]) - 1 - i) for i, bit in enumerate(bin(bytes_to_long(message))[2:]))
e = 2 ** 256
c = n ** e
print(e) ## to be given to the user
print(c) ## to be given to the user
print(p * q) ## to be given to the user
Trong bài này chúng ta có đa thức modulo \(p(x) \cdot q(x)\). Flag được biến đổi thành dãy nhị phân và là hệ số cho đa thức \(n(x) \bmod{p(x) \cdot q(x)}\). Ciphertext khi đó là \(n(x)^e \bmod{p(x) \cdot q(x)}\).
Chúng ta làm tương tự RSA, factor modulus. Tiếp theo, gọi \(d_p = \deg p(x)\) thì số phần tử khác 0 trong \(\mathrm{GF} (2^{d_p})\) là \(2^{d_p} - 1\). Tương tự cho \(q(x)\) số phần tử khác \(0\) là \(2^{d_q} - 1\). Do đó mình tính nghịch đảo của \(e = 2^{256}\) trong modulus \((2^{d_p} - 1) \cdot (2^{d_q} - 1)\).
from Crypto.Util.number import long_to_bytes
e = 115792089237316195423570985008687907853269984665640564039457584007913129639936
F.<x> = PolynomialRing(GF(2))
n = x^4547 + x^3524 + x^3518 + x^3517 + x^3512 + x^1072 + x^1070 + x^1041 + x^1035 + x^49 + x^47 + x^43 + x^42 + x^41 + x^40 + x^37 + x^35 + x^18 + x^11 + x^5 + 1
p, q = [[0] for _ in list(factor(n))]
R.<y> = F.quotient_ring(p * q)
c = y^4546 + y^4540 + y^4536 + y^4534 + y^4533 + y^4532 + y^4530 + y^4527 + y^4525 + y^4522 + y^4520 + y^4518 + y^4517 + y^4516 + y^4514 + y^4513 + y^4512 + y^4510 + y^4509 + y^4507 + y^4505 + y^4500 + y^4498 + y^4497 + y^4495 + y^4494 + y^4487 + y^4486 + y^4484 + y^4483 + y^4480 + y^4479 + y^4476 + y^4473 + y^4471 + y^4470 + y^4469 + y^4467 + y^4466 + y^4463 + y^4462 + y^4461 + y^4455 + y^4454 + y^4452 + y^4451 + y^4450 + y^4446 + y^4445 + y^4444 + y^4443 + y^4441 + y^4439 + y^4438 + y^4436 + y^4434 + y^4433 + y^4432 + y^4429 + y^4427 + y^4424 + y^4422 + y^4420 + y^4418 + y^4417 + y^4416 + y^4413 + y^4412 + y^4410 + y^4409 + y^4408 + y^4403 + y^4402 + y^4400 + y^4399 + y^4397 + y^4396 + y^4395 + y^4394 + y^4392 + y^4390 + y^4388 + y^4387 + y^4383 + y^4382 + y^4380 + y^4378 + y^4375 + y^4373 + y^4372 + y^4370 + y^4368 + y^4366 + y^4364 + y^4363 + y^4359 + y^4355 + y^4354 + y^4352 + y^4350 + y^4349 + y^4348 + y^4345 + y^4344 + y^4342 + y^4341 + y^4340 + y^4339 + y^4338 + y^4336 + y^4335 + y^4334 + y^4333 + y^4327 + y^4326 + y^4325 + y^4322 + y^4318 + y^4315 + y^4314 + y^4313 + y^4312 + y^4307 + y^4306 + y^4304 + y^4302 + y^4300 + y^4298 + y^4297 + y^4294 + y^4293 + y^4288 + y^4285 + y^4283 + y^4281 + y^4280 + y^4278 + y^4277 + y^4276 + y^4275 + y^4271 + y^4270 + y^4269 + y^4268 + y^4265 + y^4264 + y^4263 + y^4262 + y^4261 + y^4259 + y^4253 + y^4252 + y^4250 + y^4247 + y^4246 + y^4245 + y^4242 + y^4240 + y^4239 + y^4236 + y^4234 + y^4232 + y^4230 + y^4229 + y^4227 + y^4223 + y^4220 + y^4219 + y^4218 + y^4217 + y^4212 + y^4209 + y^4203 + y^4202 + y^4200 + y^4199 + y^4197 + y^4194 + y^4191 + y^4190 + y^4189 + y^4187 + y^4186 + y^4185 + y^4184 + y^4182 + y^4176 + y^4174 + y^4172 + y^4168 + y^4167 + y^4166 + y^4164 + y^4163 + y^4161 + y^4160 + y^4157 + y^4155 + y^4154 + y^4153 + y^4151 + y^4146 + y^4142 + y^4140 + y^4139 + y^4138 + y^4137 + y^4136 + y^4135 + y^4130 + y^4129 + y^4128 + y^4125 + y^4123 + y^4120 + y^4119 + y^4114 + y^4113 + y^4109 + y^4107 + y^4106 + y^4100 + y^4097 + y^4096 + y^4089 + y^4088 + y^4087 + y^4084 + y^4083 + y^4082 + y^4080 + y^4079 + y^4076 + y^4072 + y^4071 + y^4070 + y^4068 + y^4067 + y^4066 + y^4065 + y^4064 + y^4063 + y^4061 + y^4058 + y^4055 + y^4054 + y^4052 + y^4051 + y^4048 + y^4047 + y^4046 + y^4045 + y^4043 + y^4042 + y^4040 + y^4039 + y^4037 + y^4036 + y^4034 + y^4033 + y^4032 + y^4029 + y^4027 + y^4026 + y^4022 + y^4019 + y^4018 + y^4016 + y^4014 + y^4013 + y^4009 + y^4007 + y^4005 + y^4001 + y^3999 + y^3997 + y^3996 + y^3995 + y^3994 + y^3992 + y^3991 + y^3990 + y^3988 + y^3987 + y^3986 + y^3984 + y^3980 + y^3979 + y^3977 + y^3975 + y^3974 + y^3973 + y^3972 + y^3971 + y^3970 + y^3969 + y^3966 + y^3965 + y^3964 + y^3963 + y^3962 + y^3961 + y^3960 + y^3957 + y^3955 + y^3950 + y^3948 + y^3946 + y^3945 + y^3943 + y^3939 + y^3936 + y^3934 + y^3933 + y^3932 + y^3931 + y^3930 + y^3929 + y^3928 + y^3926 + y^3925 + y^3921 + y^3918 + y^3917 + y^3915 + y^3914 + y^3913 + y^3909 + y^3907 + y^3906 + y^3905 + y^3904 + y^3903 + y^3902 + y^3901 + y^3900 + y^3899 + y^3898 + y^3897 + y^3896 + y^3895 + y^3894 + y^3892 + y^3889 + y^3886 + y^3881 + y^3880 + y^3879 + y^3873 + y^3872 + y^3870 + y^3868 + y^3866 + y^3865 + y^3861 + y^3860 + y^3859 + y^3857 + y^3855 + y^3854 + y^3853 + y^3852 + y^3851 + y^3850 + y^3848 + y^3847 + y^3843 + y^3841 + y^3839 + y^3837 + y^3835 + y^3834 + y^3833 + y^3832 + y^3829 + y^3828 + y^3826 + y^3825 + y^3823 + y^3822 + y^3819 + y^3817 + y^3815 + y^3807 + y^3805 + y^3804 + y^3803 + y^3802 + y^3800 + y^3799 + y^3798 + y^3795 + y^3794 + y^3792 + y^3790 + y^3787 + y^3786 + y^3783 + y^3782 + y^3780 + y^3779 + y^3778 + y^3776 + y^3775 + y^3774 + y^3773 + y^3772 + y^3771 + y^3769 + y^3768 + y^3767 + y^3766 + y^3765 + y^3764 + y^3762 + y^3761 + y^3758 + y^3757 + y^3755 + y^3753 + y^3752 + y^3750 + y^3749 + y^3747 + y^3746 + y^3745 + y^3744 + y^3743 + y^3742 + y^3741 + y^3739 + y^3737 + y^3736 + y^3734 + y^3732 + y^3730 + y^3727 + y^3725 + y^3723 + y^3720 + y^3719 + y^3715 + y^3714 + y^3712 + y^3709 + y^3708 + y^3706 + y^3705 + y^3702 + y^3700 + y^3697 + y^3695 + y^3694 + y^3692 + y^3689 + y^3688 + y^3687 + y^3686 + y^3683 + y^3681 + y^3680 + y^3675 + y^3672 + y^3671 + y^3669 + y^3667 + y^3666 + y^3665 + y^3663 + y^3661 + y^3657 + y^3655 + y^3654 + y^3652 + y^3651 + y^3650 + y^3649 + y^3648 + y^3647 + y^3645 + y^3644 + y^3643 + y^3641 + y^3639 + y^3637 + y^3634 + y^3632 + y^3631 + y^3630 + y^3629 + y^3625 + y^3624 + y^3622 + y^3620 + y^3616 + y^3614 + y^3613 + y^3612 + y^3610 + y^3603 + y^3602 + y^3600 + y^3597 + y^3596 + y^3592 + y^3590 + y^3589 + y^3588 + y^3584 + y^3580 + y^3578 + y^3577 + y^3576 + y^3573 + y^3572 + y^3569 + y^3568 + y^3566 + y^3565 + y^3562 + y^3561 + y^3560 + y^3559 + y^3558 + y^3556 + y^3555 + y^3552 + y^3551 + y^3550 + y^3547 + y^3544 + y^3542 + y^3540 + y^3537 + y^3534 + y^3530 + y^3529 + y^3527 + y^3526 + y^3525 + y^3524 + y^3523 + y^3522 + y^3521 + y^3517 + y^3516 + y^3515 + y^3514 + y^3513 + y^3511 + y^3510 + y^3509 + y^3508 + y^3507 + y^3505 + y^3504 + y^3503 + y^3502 + y^3497 + y^3496 + y^3493 + y^3491 + y^3490 + y^3486 + y^3485 + y^3483 + y^3482 + y^3480 + y^3479 + y^3477 + y^3476 + y^3475 + y^3473 + y^3469 + y^3463 + y^3462 + y^3461 + y^3456 + y^3451 + y^3450 + y^3449 + y^3448 + y^3447 + y^3444 + y^3443 + y^3442 + y^3438 + y^3437 + y^3436 + y^3435 + y^3434 + y^3433 + y^3432 + y^3431 + y^3427 + y^3426 + y^3423 + y^3422 + y^3421 + y^3419 + y^3418 + y^3415 + y^3413 + y^3411 + y^3407 + y^3406 + y^3404 + y^3402 + y^3401 + y^3395 + y^3394 + y^3393 + y^3391 + y^3387 + y^3386 + y^3385 + y^3384 + y^3382 + y^3381 + y^3380 + y^3379 + y^3378 + y^3376 + y^3375 + y^3374 + y^3372 + y^3370 + y^3368 + y^3367 + y^3365 + y^3364 + y^3363 + y^3359 + y^3356 + y^3355 + y^3354 + y^3353 + y^3351 + y^3349 + y^3339 + y^3335 + y^3334 + y^3327 + y^3326 + y^3324 + y^3323 + y^3322 + y^3321 + y^3320 + y^3319 + y^3317 + y^3316 + y^3313 + y^3311 + y^3310 + y^3306 + y^3304 + y^3303 + y^3301 + y^3300 + y^3299 + y^3298 + y^3295 + y^3293 + y^3291 + y^3289 + y^3285 + y^3284 + y^3283 + y^3280 + y^3278 + y^3276 + y^3274 + y^3272 + y^3270 + y^3269 + y^3268 + y^3261 + y^3260 + y^3257 + y^3256 + y^3252 + y^3247 + y^3246 + y^3244 + y^3242 + y^3241 + y^3239 + y^3238 + y^3237 + y^3234 + y^3233 + y^3231 + y^3230 + y^3229 + y^3228 + y^3227 + y^3226 + y^3224 + y^3223 + y^3219 + y^3218 + y^3217 + y^3216 + y^3215 + y^3214 + y^3210 + y^3209 + y^3207 + y^3205 + y^3201 + y^3194 + y^3193 + y^3191 + y^3190 + y^3186 + y^3185 + y^3181 + y^3179 + y^3177 + y^3175 + y^3171 + y^3167 + y^3166 + y^3165 + y^3164 + y^3162 + y^3161 + y^3159 + y^3157 + y^3152 + y^3149 + y^3148 + y^3146 + y^3144 + y^3140 + y^3138 + y^3135 + y^3134 + y^3133 + y^3131 + y^3130 + y^3129 + y^3127 + y^3126 + y^3124 + y^3122 + y^3120 + y^3119 + y^3118 + y^3117 + y^3115 + y^3114 + y^3113 + y^3112 + y^3110 + y^3109 + y^3106 + y^3105 + y^3100 + y^3098 + y^3097 + y^3094 + y^3093 + y^3092 + y^3089 + y^3087 + y^3083 + y^3080 + y^3077 + y^3075 + y^3074 + y^3073 + y^3066 + y^3062 + y^3061 + y^3060 + y^3059 + y^3051 + y^3050 + y^3047 + y^3043 + y^3042 + y^3041 + y^3040 + y^3037 + y^3034 + y^3032 + y^3030 + y^3029 + y^3025 + y^3023 + y^3022 + y^3019 + y^3018 + y^3017 + y^3015 + y^3013 + y^3010 + y^3005 + y^3002 + y^3000 + y^2999 + y^2998 + y^2997 + y^2996 + y^2995 + y^2994 + y^2993 + y^2990 + y^2988 + y^2987 + y^2986 + y^2985 + y^2983 + y^2982 + y^2980 + y^2977 + y^2976 + y^2975 + y^2972 + y^2971 + y^2970 + y^2969 + y^2966 + y^2965 + y^2964 + y^2962 + y^2961 + y^2960 + y^2957 + y^2956 + y^2954 + y^2953 + y^2952 + y^2951 + y^2949 + y^2948 + y^2946 + y^2944 + y^2943 + y^2942 + y^2941 + y^2940 + y^2938 + y^2936 + y^2933 + y^2930 + y^2924 + y^2922 + y^2919 + y^2916 + y^2915 + y^2911 + y^2909 + y^2908 + y^2905 + y^2904 + y^2902 + y^2901 + y^2900 + y^2898 + y^2891 + y^2885 + y^2884 + y^2883 + y^2881 + y^2878 + y^2874 + y^2871 + y^2868 + y^2867 + y^2865 + y^2863 + y^2862 + y^2860 + y^2858 + y^2856 + y^2854 + y^2852 + y^2851 + y^2848 + y^2846 + y^2844 + y^2843 + y^2840 + y^2839 + y^2837 + y^2836 + y^2832 + y^2829 + y^2828 + y^2827 + y^2826 + y^2825 + y^2819 + y^2816 + y^2815 + y^2813 + y^2812 + y^2808 + y^2807 + y^2806 + y^2804 + y^2800 + y^2799 + y^2798 + y^2794 + y^2793 + y^2792 + y^2791 + y^2790 + y^2782 + y^2781 + y^2780 + y^2778 + y^2775 + y^2772 + y^2771 + y^2769 + y^2768 + y^2767 + y^2763 + y^2762 + y^2760 + y^2759 + y^2758 + y^2757 + y^2756 + y^2755 + y^2754 + y^2753 + y^2752 + y^2750 + y^2749 + y^2747 + y^2745 + y^2740 + y^2736 + y^2735 + y^2734 + y^2733 + y^2732 + y^2731 + y^2728 + y^2727 + y^2723 + y^2722 + y^2721 + y^2719 + y^2717 + y^2716 + y^2714 + y^2712 + y^2711 + y^2710 + y^2709 + y^2708 + y^2707 + y^2706 + y^2704 + y^2703 + y^2701 + y^2700 + y^2699 + y^2698 + y^2696 + y^2695 + y^2694 + y^2693 + y^2689 + y^2684 + y^2680 + y^2678 + y^2672 + y^2671 + y^2670 + y^2667 + y^2665 + y^2663 + y^2659 + y^2657 + y^2656 + y^2654 + y^2653 + y^2651 + y^2650 + y^2648 + y^2646 + y^2644 + y^2643 + y^2642 + y^2640 + y^2639 + y^2636 + y^2632 + y^2629 + y^2628 + y^2627 + y^2625 + y^2622 + y^2619 + y^2618 + y^2615 + y^2613 + y^2612 + y^2611 + y^2610 + y^2609 + y^2608 + y^2606 + y^2602 + y^2601 + y^2600 + y^2599 + y^2597 + y^2594 + y^2589 + y^2587 + y^2585 + y^2584 + y^2582 + y^2580 + y^2578 + y^2577 + y^2574 + y^2573 + y^2572 + y^2570 + y^2569 + y^2568 + y^2554 + y^2553 + y^2552 + y^2549 + y^2548 + y^2546 + y^2545 + y^2544 + y^2543 + y^2541 + y^2536 + y^2534 + y^2533 + y^2532 + y^2531 + y^2530 + y^2527 + y^2526 + y^2525 + y^2520 + y^2516 + y^2514 + y^2512 + y^2508 + y^2507 + y^2506 + y^2505 + y^2502 + y^2501 + y^2496 + y^2495 + y^2492 + y^2491 + y^2490 + y^2487 + y^2486 + y^2483 + y^2482 + y^2480 + y^2476 + y^2473 + y^2471 + y^2468 + y^2467 + y^2465 + y^2463 + y^2462 + y^2455 + y^2454 + y^2452 + y^2451 + y^2450 + y^2446 + y^2445 + y^2443 + y^2442 + y^2441 + y^2435 + y^2434 + y^2433 + y^2431 + y^2430 + y^2429 + y^2428 + y^2427 + y^2425 + y^2423 + y^2422 + y^2420 + y^2419 + y^2417 + y^2416 + y^2415 + y^2412 + y^2410 + y^2406 + y^2402 + y^2399 + y^2398 + y^2397 + y^2396 + y^2395 + y^2394 + y^2391 + y^2387 + y^2385 + y^2384 + y^2378 + y^2376 + y^2372 + y^2371 + y^2368 + y^2366 + y^2365 + y^2364 + y^2360 + y^2357 + y^2356 + y^2355 + y^2354 + y^2351 + y^2349 + y^2348 + y^2346 + y^2345 + y^2343 + y^2342 + y^2341 + y^2339 + y^2336 + y^2333 + y^2331 + y^2330 + y^2328 + y^2327 + y^2325 + y^2324 + y^2321 + y^2314 + y^2310 + y^2309 + y^2303 + y^2302 + y^2301 + y^2296 + y^2295 + y^2294 + y^2292 + y^2291 + y^2290 + y^2289 + y^2288 + y^2286 + y^2285 + y^2284 + y^2283 + y^2282 + y^2277 + y^2275 + y^2273 + y^2272 + y^2271 + y^2270 + y^2267 + y^2265 + y^2263 + y^2262 + y^2260 + y^2259 + y^2258 + y^2254 + y^2252 + y^2251 + y^2248 + y^2246 + y^2243 + y^2236 + y^2234 + y^2233 + y^2232 + y^2230 + y^2227 + y^2226 + y^2224 + y^2223 + y^2221 + y^2220 + y^2219 + y^2213 + y^2211 + y^2208 + y^2207 + y^2204 + y^2201 + y^2200 + y^2196 + y^2195 + y^2194 + y^2193 + y^2192 + y^2189 + y^2185 + y^2182 + y^2181 + y^2179 + y^2177 + y^2175 + y^2173 + y^2172 + y^2170 + y^2168 + y^2167 + y^2165 + y^2154 + y^2153 + y^2151 + y^2150 + y^2149 + y^2147 + y^2146 + y^2142 + y^2141 + y^2139 + y^2138 + y^2134 + y^2133 + y^2131 + y^2130 + y^2127 + y^2121 + y^2119 + y^2117 + y^2114 + y^2112 + y^2111 + y^2110 + y^2108 + y^2104 + y^2100 + y^2097 + y^2094 + y^2093 + y^2091 + y^2088 + y^2083 + y^2082 + y^2081 + y^2076 + y^2073 + y^2072 + y^2071 + y^2070 + y^2069 + y^2068 + y^2066 + y^2064 + y^2063 + y^2061 + y^2058 + y^2056 + y^2055 + y^2052 + y^2050 + y^2049 + y^2046 + y^2045 + y^2044 + y^2043 + y^2041 + y^2038 + y^2036 + y^2031 + y^2030 + y^2028 + y^2026 + y^2025 + y^2023 + y^2022 + y^2021 + y^2020 + y^2016 + y^2014 + y^2012 + y^2011 + y^2009 + y^2005 + y^2001 + y^1998 + y^1997 + y^1994 + y^1993 + y^1992 + y^1991 + y^1981 + y^1978 + y^1975 + y^1972 + y^1971 + y^1970 + y^1969 + y^1966 + y^1965 + y^1964 + y^1960 + y^1956 + y^1945 + y^1942 + y^1940 + y^1938 + y^1935 + y^1934 + y^1933 + y^1931 + y^1930 + y^1929 + y^1927 + y^1926 + y^1924 + y^1923 + y^1922 + y^1919 + y^1918 + y^1917 + y^1911 + y^1910 + y^1909 + y^1907 + y^1906 + y^1904 + y^1903 + y^1901 + y^1900 + y^1899 + y^1896 + y^1895 + y^1893 + y^1892 + y^1890 + y^1889 + y^1888 + y^1887 + y^1886 + y^1885 + y^1884 + y^1882 + y^1881 + y^1877 + y^1869 + y^1866 + y^1865 + y^1862 + y^1858 + y^1856 + y^1855 + y^1848 + y^1846 + y^1845 + y^1844 + y^1842 + y^1841 + y^1840 + y^1836 + y^1834 + y^1831 + y^1828 + y^1827 + y^1825 + y^1824 + y^1822 + y^1818 + y^1817 + y^1809 + y^1807 + y^1806 + y^1803 + y^1797 + y^1796 + y^1795 + y^1793 + y^1791 + y^1790 + y^1786 + y^1785 + y^1782 + y^1781 + y^1778 + y^1776 + y^1774 + y^1773 + y^1772 + y^1771 + y^1770 + y^1768 + y^1764 + y^1761 + y^1759 + y^1758 + y^1757 + y^1753 + y^1751 + y^1750 + y^1747 + y^1746 + y^1745 + y^1744 + y^1742 + y^1741 + y^1740 + y^1739 + y^1738 + y^1735 + y^1732 + y^1729 + y^1728 + y^1726 + y^1725 + y^1721 + y^1719 + y^1718 + y^1715 + y^1714 + y^1713 + y^1711 + y^1710 + y^1708 + y^1705 + y^1704 + y^1703 + y^1702 + y^1701 + y^1700 + y^1699 + y^1697 + y^1696 + y^1694 + y^1693 + y^1691 + y^1690 + y^1686 + y^1685 + y^1684 + y^1682 + y^1679 + y^1678 + y^1677 + y^1676 + y^1673 + y^1671 + y^1670 + y^1669 + y^1668 + y^1666 + y^1664 + y^1663 + y^1662 + y^1660 + y^1659 + y^1653 + y^1649 + y^1648 + y^1644 + y^1643 + y^1641 + y^1640 + y^1639 + y^1633 + y^1631 + y^1629 + y^1625 + y^1624 + y^1617 + y^1612 + y^1608 + y^1607 + y^1606 + y^1602 + y^1601 + y^1600 + y^1594 + y^1593 + y^1591 + y^1590 + y^1589 + y^1587 + y^1586 + y^1585 + y^1584 + y^1583 + y^1581 + y^1580 + y^1575 + y^1573 + y^1568 + y^1563 + y^1562 + y^1558 + y^1557 + y^1556 + y^1554 + y^1553 + y^1551 + y^1550 + y^1548 + y^1547 + y^1544 + y^1543 + y^1541 + y^1540 + y^1536 + y^1534 + y^1531 + y^1530 + y^1529 + y^1528 + y^1527 + y^1526 + y^1524 + y^1523 + y^1521 + y^1516 + y^1513 + y^1510 + y^1508 + y^1505 + y^1503 + y^1501 + y^1500 + y^1497 + y^1493 + y^1490 + y^1489 + y^1488 + y^1487 + y^1484 + y^1478 + y^1477 + y^1475 + y^1474 + y^1473 + y^1472 + y^1471 + y^1467 + y^1466 + y^1463 + y^1461 + y^1459 + y^1458 + y^1457 + y^1455 + y^1454 + y^1452 + y^1448 + y^1447 + y^1446 + y^1444 + y^1443 + y^1442 + y^1439 + y^1438 + y^1436 + y^1433 + y^1432 + y^1426 + y^1423 + y^1422 + y^1419 + y^1418 + y^1416 + y^1413 + y^1409 + y^1407 + y^1406 + y^1404 + y^1403 + y^1401 + y^1398 + y^1397 + y^1395 + y^1393 + y^1391 + y^1390 + y^1389 + y^1387 + y^1385 + y^1384 + y^1380 + y^1379 + y^1376 + y^1374 + y^1373 + y^1372 + y^1364 + y^1363 + y^1361 + y^1359 + y^1356 + y^1354 + y^1353 + y^1350 + y^1349 + y^1348 + y^1347 + y^1346 + y^1344 + y^1343 + y^1342 + y^1341 + y^1340 + y^1339 + y^1338 + y^1337 + y^1334 + y^1332 + y^1327 + y^1326 + y^1325 + y^1324 + y^1323 + y^1322 + y^1319 + y^1316 + y^1315 + y^1312 + y^1311 + y^1307 + y^1305 + y^1303 + y^1302 + y^1298 + y^1296 + y^1295 + y^1294 + y^1291 + y^1290 + y^1289 + y^1288 + y^1287 + y^1286 + y^1284 + y^1283 + y^1282 + y^1281 + y^1278 + y^1276 + y^1271 + y^1270 + y^1267 + y^1264 + y^1263 + y^1261 + y^1260 + y^1258 + y^1257 + y^1256 + y^1255 + y^1254 + y^1252 + y^1250 + y^1249 + y^1248 + y^1246 + y^1243 + y^1242 + y^1239 + y^1237 + y^1231 + y^1227 + y^1225 + y^1220 + y^1219 + y^1218 + y^1217 + y^1216 + y^1214 + y^1212 + y^1210 + y^1206 + y^1205 + y^1203 + y^1202 + y^1195 + y^1192 + y^1190 + y^1189 + y^1187 + y^1185 + y^1183 + y^1182 + y^1181 + y^1179 + y^1178 + y^1172 + y^1169 + y^1168 + y^1165 + y^1164 + y^1163 + y^1159 + y^1158 + y^1157 + y^1154 + y^1151 + y^1150 + y^1148 + y^1147 + y^1146 + y^1144 + y^1143 + y^1142 + y^1140 + y^1137 + y^1132 + y^1131 + y^1128 + y^1127 + y^1120 + y^1119 + y^1118 + y^1117 + y^1115 + y^1110 + y^1109 + y^1108 + y^1104 + y^1102 + y^1101 + y^1100 + y^1095 + y^1093 + y^1092 + y^1089 + y^1085 + y^1081 + y^1078 + y^1075 + y^1073 + y^1071 + y^1069 + y^1067 + y^1066 + y^1065 + y^1064 + y^1063 + y^1062 + y^1059 + y^1058 + y^1056 + y^1055 + y^1053 + y^1051 + y^1048 + y^1047 + y^1046 + y^1044 + y^1043 + y^1042 + y^1041 + y^1040 + y^1039 + y^1037 + y^1034 + y^1033 + y^1032 + y^1031 + y^1030 + y^1028 + y^1024 + y^1023 + y^1022 + y^1021 + y^1020 + y^1019 + y^1018 + y^1017 + y^1015 + y^1013 + y^1012 + y^1009 + y^1008 + y^1007 + y^1005 + y^1002 + y^1000 + y^995 + y^988 + y^985 + y^984 + y^980 + y^979 + y^977 + y^976 + y^973 + y^970 + y^969 + y^967 + y^964 + y^961 + y^960 + y^958 + y^955 + y^953 + y^951 + y^949 + y^940 + y^937 + y^936 + y^935 + y^931 + y^930 + y^929 + y^928 + y^926 + y^924 + y^923 + y^921 + y^918 + y^917 + y^909 + y^907 + y^906 + y^904 + y^903 + y^901 + y^899 + y^898 + y^897 + y^896 + y^894 + y^892 + y^891 + y^888 + y^886 + y^884 + y^881 + y^878 + y^877 + y^876 + y^873 + y^870 + y^869 + y^868 + y^866 + y^861 + y^858 + y^856 + y^855 + y^853 + y^851 + y^850 + y^849 + y^848 + y^846 + y^845 + y^842 + y^839 + y^838 + y^835 + y^832 + y^828 + y^825 + y^824 + y^821 + y^819 + y^816 + y^812 + y^806 + y^805 + y^803 + y^802 + y^801 + y^799 + y^794 + y^793 + y^791 + y^789 + y^784 + y^780 + y^779 + y^777 + y^776 + y^774 + y^773 + y^771 + y^770 + y^769 + y^766 + y^765 + y^761 + y^760 + y^758 + y^757 + y^755 + y^750 + y^749 + y^748 + y^746 + y^745 + y^743 + y^741 + y^739 + y^738 + y^736 + y^734 + y^733 + y^731 + y^730 + y^728 + y^726 + y^723 + y^718 + y^717 + y^716 + y^714 + y^712 + y^711 + y^709 + y^703 + y^701 + y^700 + y^699 + y^696 + y^695 + y^692 + y^691 + y^689 + y^686 + y^683 + y^677 + y^673 + y^671 + y^667 + y^659 + y^655 + y^654 + y^652 + y^649 + y^648 + y^647 + y^646 + y^645 + y^644 + y^642 + y^637 + y^635 + y^633 + y^628 + y^623 + y^620 + y^615 + y^613 + y^612 + y^611 + y^610 + y^609 + y^608 + y^607 + y^603 + y^602 + y^599 + y^598 + y^596 + y^595 + y^593 + y^590 + y^589 + y^588 + y^587 + y^586 + y^585 + y^583 + y^580 + y^579 + y^567 + y^562 + y^560 + y^559 + y^558 + y^557 + y^555 + y^553 + y^552 + y^551 + y^550 + y^549 + y^548 + y^547 + y^545 + y^544 + y^541 + y^540 + y^539 + y^537 + y^535 + y^534 + y^533 + y^531 + y^529 + y^528 + y^527 + y^526 + y^524 + y^523 + y^521 + y^519 + y^518 + y^517 + y^516 + y^514 + y^512 + y^511 + y^510 + y^508 + y^506 + y^505 + y^499 + y^498 + y^496 + y^493 + y^491 + y^490 + y^488 + y^484 + y^483 + y^477 + y^474 + y^473 + y^472 + y^471 + y^466 + y^463 + y^462 + y^461 + y^459 + y^457 + y^456 + y^455 + y^454 + y^450 + y^447 + y^445 + y^441 + y^440 + y^439 + y^436 + y^432 + y^429 + y^428 + y^426 + y^422 + y^421 + y^419 + y^417 + y^416 + y^415 + y^414 + y^413 + y^412 + y^411 + y^407 + y^404 + y^402 + y^401 + y^399 + y^396 + y^395 + y^394 + y^392 + y^389 + y^388 + y^385 + y^382 + y^380 + y^379 + y^378 + y^377 + y^374 + y^373 + y^371 + y^368 + y^367 + y^365 + y^361 + y^357 + y^355 + y^354 + y^353 + y^349 + y^344 + y^341 + y^340 + y^338 + y^336 + y^335 + y^334 + y^331 + y^329 + y^325 + y^324 + y^323 + y^320 + y^318 + y^314 + y^309 + y^306 + y^303 + y^299 + y^298 + y^297 + y^296 + y^295 + y^292 + y^290 + y^289 + y^286 + y^285 + y^282 + y^281 + y^280 + y^278 + y^275 + y^269 + y^267 + y^265 + y^263 + y^261 + y^259 + y^258 + y^256 + y^253 + y^251 + y^247 + y^246 + y^244 + y^242 + y^240 + y^237 + y^235 + y^232 + y^229 + y^226 + y^225 + y^224 + y^223 + y^220 + y^216 + y^213 + y^212 + y^211 + y^209 + y^208 + y^207 + y^206 + y^203 + y^202 + y^201 + y^200 + y^197 + y^196 + y^195 + y^194 + y^193 + y^190 + y^187 + y^184 + y^183 + y^182 + y^180 + y^179 + y^178 + y^177 + y^176 + y^174 + y^173 + y^172 + y^171 + y^170 + y^168 + y^164 + y^162 + y^161 + y^160 + y^158 + y^156 + y^153 + y^152 + y^150 + y^148 + y^143 + y^140 + y^139 + y^138 + y^134 + y^131 + y^130 + y^124 + y^122 + y^119 + y^117 + y^116 + y^115 + y^112 + y^106 + y^100 + y^99 + y^98 + y^97 + y^96 + y^95 + y^94 + y^92 + y^88 + y^86 + y^83 + y^81 + y^78 + y^77 + y^75 + y^69 + y^67 + y^66 + y^65 + y^64 + y^62 + y^57 + y^54 + y^52 + y^50 + y^49 + y^48 + y^45 + y^42 + y^33 + y^26 + y^23 + y^22 + y^20 + y^19 + y^18 + y^17 + y^16 + y^14 + y^10 + y^9 + y^7 + y^6 + y^5 + y^4 + y^3 + y^2
dp, dq = p.degree(), q.degree()
d = inverse_mod(e, (2^dp-1)*(2^dq-1))
m = c**d
m = "".join(map(str, list(m)[::-1]))
print(long_to_bytes(int(m, 2)))
# b'flag{S0_1mPL3m3n71nG_R54_0n_P0lYn0m1aL5_1n5734d_d1dn7_w0rk_hUh!!?}'
Knapsack¶
import random
import hashlib
from Crypto.Util.number import bytes_to_long
from Crypto.Cipher import AES
flag = b"The flag has been REDACTED"
secret = b"The seccret has been REDACTED"
key = hashlib.sha256(secret).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
padded_flag = flag + b'\x00'*(-len(flag)%16)
ciphertext = cipher.encrypt(padded_flag)
f = open('output.txt','w')
f.write(f"Ciphertext: {ciphertext.hex()}\n\n")
arr = [ random.randint(1,1000000000000) for i in range(40) ]
k = bytes_to_long(secret)
s = 0
for i in range(40):
if k&(1<<i):
s+=arr[i]
f.write(f'numbers: {str(arr)[1:-1]}\nsum: {s}\n')
f.close()
Đề bài cho mình một mảng arr và tùy vào bit của secret mà cộng arr vào \(s\) hoặc không. Điều này gợi nhớ về sử dụng lattice để giải bài toán knapsack. Mình tham khảo trong quyển An introduction to mathematical cryptography và xây dựng lattice như sau:
\[\begin{split}A_{M, S} = \begin{pmatrix}
2 & 0 & 0 & \cdots & 0 & a_0 \\
0 & 2 & 0 & \cdots & 0 & a_1 \\
0 & 0 & 2 & \cdots & 0 & a_2 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & \cdots & 2 & a_{39} \\
1 & 1 & 1 & \cdots & 1 & s
\end{pmatrix}\end{split}\]
Sử dụng thuật toán BKZ trên ma trận \(A_{M, S}\) trên được dòng đầu là \(\bar{n}\), nhân \(\bar{n}\) với \(A_{M, S}^{-1}\) ta được flag.
Note: thuật toán LLL không hiệu quả ở đây còn thuật toán BKZ được sử dụng là do BKZ tốt hơn trong việc giải SVP nhưng chạy lâu hơn (theo giải thích của 1 bạn trong discord giải).
from sage.all import *
from itertools import product
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib
arr = [600848253359, 617370603129, 506919465064, 218995773533, 831016169202, 501743312177, 15915022145, 902217876313, 16106924577, 339484425400, 372255158657, 612977795139, 755932592051, 188931588244, 266379866558, 661628157071, 428027838199, 929094803770, 917715204448, 103431741147, 549163664804, 398306592361, 442876575930, 641158284784, 492384131229, 524027495955, 232203211652, 213223394430, 322608432478, 721091079509, 518513918024, 397397503488, 62846154328, 725196249396, 443022485079, 547194537747, 348150826751, 522851553238, 421636467374, 12712949979]
s = 7929089016814
M = matrix(ZZ, len(arr) + 1, len(arr) + 1)
for i in range(len(arr)):
M[i, len(arr)] = arr[i]
M[i, i] = 2
M[len(arr), i] = 1
M[len(arr), len(arr)] = s
N = M.BKZ()
ciphertext = bytes.fromhex('af95a58f4fbab33cd98f2bfcdcd19a101c04232ac6e8f7e9b705b942be9707b66ac0e62ed38f14046d1cd86b133ebda9')
t = (N[0]*M.inverse())[:-1]
secret = [0 if _ == 0 else 1 for _ in t][::-1]
assert len(secret) == 40
secret = int("".join(map(str, secret)), 2)
secret = long_to_bytes(secret)
key = hashlib.sha256(secret).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ciphertext)
if b'flag' in flag: print(flag)
# b'flag{N0t_r34dy_f0r_M3rkl3-H3llman}\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
Curvy Curves¶
from Crypto.Util.number import getRandomNBitInteger, bytes_to_long, long_to_bytes
from sage.all import *
# non-residue
D = 136449572493235894105040063345648963382768741227829225155873529439788000141924302071247144068377223170502438469323595278711906213653227972959011573520003821372215616761555719247287249928879121278574549473346526897917771460153933981713383608662604675157541813068900456012262173614716378648849079776150946352466
# redacted
p = "REDACTED"
q = "REDACTED"
# n = p*q
n = 22409692526386997228129877156813506752754387447752717527887987964559571432427892983480051412477389130668335262274931995291504411262883294295070539542625671556700675266826067588284189832712291138415510613208544808040871773692292843299067831286462494693987261585149330989738677007709580904907799587705949221601393
flag = b"flag{REDACTED}"
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __add__(self, other):
x = (self.x*other.x + D*self.y*other.y)%n
y = (self.y*other.x + self.x*other.y)%n
return Point(x, y)
def __mul__(self, d):
Q = Point(1, 0)
P = Point(self.x, self.y)
while d != 0:
if d&1 == 1:
Q += P
P += P
d >>= 1
return Q
def __str__(self) -> str:
return f"{self.x}, {self.y}"
def check_residue(y):
if pow(y, (p - 1)//2, p) == 1 and pow(y, (q - 1)//2, q) == 1:
return True
return False
def gen_point():
while True:
x = getRandomNBitInteger(1023 - 240)
x = bytes_to_long(flag + long_to_bytes(x))
x %= n
y2 = ((x*x - 1)*pow(D, -1, n))%n
if(check_residue(y2)):
yp = pow(y2, (p + 1) // 4, p)
yq = pow(y2, (q + 1) // 4, q)
y = crt([yp, yq], [p, q])
return Point(x, y)
M = gen_point()
e = 65537
C = M*e
print(C)
# Cx = 10800064805285540717966506671755608695842888167470823375167618999987859282439818341340065691157186820773262778917703163576074192246707402694994764789796637450974439232033955461105503709247073521710698748730331929281150539060841390912041191898310821665024428887410019391364779755961320507576829130434805472435025, Cy = 2768587745458504508888671295007858261576650648888677215556202595582810243646501012099700700934297424175692110043143649129142339125437893189997882008360626232164112542648695106763870768328088062485508904856696799117514392142656010321241751972060171400632856162388575536779942744760787860721273632723718380811912
Ở bài này cần factor \(n\) là có thể giải ra. Tuy nhiên việc factor khá khó và sau giải mình mới biết là sử dụng phương pháp William \(p+1\). NHƯNG, một mạnh thường quân nào đó đã factor ra và mình chỉ lấy từ factordb về (vào ngày thứ 2 của CTF) và giải ra.
Trong bài này thực hiện việc cộng các điểm theo công thức sau. Gọi \(P = (x_P, y_P)\) và \(Q = (x_Q, y_Q)\) là tọa độ điểm \(P\) và \(Q\). Khi đó phép cộng \(R = P + Q\) là:
\[x_R = x_P \cdot x_Q + D \cdot y_P \cdot y_Q \bmod n\]
\[y_R = x_1 \cdot y_2 + x_2 \cdot y_1 \bmod n\]
Mình viết dưới dạng ma trận:
\[\begin{split}\begin{pmatrix}
x_P & D \cdot y_P \\ y_P & x_P
\end{pmatrix} \cdot \begin{pmatrix}
x_Q & D \cdot y_Q \\ y_Q & x_Q
\end{pmatrix} = \begin{pmatrix}
x_R & D \cdot y_R \\ y_R & x_R
\end{pmatrix}\end{split}\]
Khi đó mình ghi lại ma trận \(M = \begin{pmatrix} x & D \cdot y \\ y & x \end{pmatrix}\) và ciphertext là \(C = M^e = \begin{pmatrix} Cx & D \cdot Cy \\ Cy & Cx \end{pmatrix}\).
Phần này giống với RSA, mình cần tìm order của nhóm các điểm thỏa mãn \(x^2 - D \cdot y^2 \equiv 1 \pmod n\) (điều kiện này ở hàm get_point). Order của nhóm này là \((p+1) \cdot (q+1)\) nên ta chỉ cần tính \(d = e^{-1} \bmod{(p+1) \cdot (q+1)}\) và \(M = C^d\). Flag là tọa độ \(x\) của \(M\).
from sage.all import *
from Crypto.Util.number import long_to_bytes
p, q = 12591011258095671596958186047778684066366433713000083733603008978332296147605042520140224748454073644398378458146875090686440895644260506565719708746960331, 1779816733304736381084864812803761214302272494619817595962262887353495881068607828373749191179960417738609613170856737290048073479147894242862637932199748403
D = 136449572493235894105040063345648963382768741227829225155873529439788000141924302071247144068377223170502438469323595278711906213653227972959011573520003821372215616761555719247287249928879121278574549473346526897917771460153933981713383608662604675157541813068900456012262173614716378648849079776150946352466
n = 22409692526386997228129877156813506752754387447752717527887987964559571432427892983480051412477389130668335262274931995291504411262883294295070539542625671556700675266826067588284189832712291138415510613208544808040871773692292843299067831286462494693987261585149330989738677007709580904907799587705949221601393
assert p*q == n
Cx = 10800064805285540717966506671755608695842888167470823375167618999987859282439818341340065691157186820773262778917703163576074192246707402694994764789796637450974439232033955461105503709247073521710698748730331929281150539060841390912041191898310821665024428887410019391364779755961320507576829130434805472435025
Cy = 2768587745458504508888671295007858261576650648888677215556202595582810243646501012099700700934297424175692110043143649129142339125437893189997882008360626232164112542648695106763870768328088062485508904856696799117514392142656010321241751972060171400632856162388575536779942744760787860721273632723718380811912
e = 65537
d = inverse_mod(e, (p+1)*(q+1))
M = matrix(Zmod(n), [[Cx, D*Cy], [Cy, Cx]])
N = M**d
print(long_to_bytes(int(N[0][0])))
# b'flag{pHUCk_150M0rPh15m_1n70_p2}B\xf8\xe0\xb6\xb2m\x0f\x9b\n\xdb\xb7<N\x91\xb6\x16\xfc\x1f@&8\x96\xbe\xa1\xa7v\xa2\x81j\xda\xf6\xf1\xbfB^/&(\xd3\xbb\x0f\xb2e\xa8\x00\xd7\xe1\\(\xb3\xe4Jz\x1b\xa4\xb0&S\x01>tZ\xd9\xd2\xf2\xa3\xd1\xbc\x7f\xc3\x8d\x8au\xca\x83iD\xcfN\xe1"\xe4\x866\xa6\x9d\x8ad\xf1\x08\xf4\xf59\xa5*ms\xa9'
Safe Curvy Curve¶
from Crypto.Util.number import getPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
from sage.all import *
n = 325325755182481058670589439237195225483797901549838835146388756505962515992731682902174843378473793118013824587686743801443229435097379024643408429957717590072275498734396840489261986361764935791083084431387935565119970246214821662977047205360090509590387268197591520307878877103247121412898793371812283196864079961633428662039795223806526580626911586062085681619829271800589543048515261459541945856915535056363750996243146294104205192635607675773145823355324367791593757860302117944097894321078809559514655550115178790472355420484756646090492860950760854985816746318432545157312928351659730275368368710393481
# non-residue
D = 104195424559311137181271279442498654957365659039072230133307906910289876977215387204406606621273182995744469913980318794193540266885069529501579897759819085330481440863835062469771268905581027223137570462332151650553239341513789960350350245008144164176339007365876329719830893966710072622193879546377346644622
# redacted
p = "REDACTED"
q = n // p
flag = b"REDACTED"
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __add__(self, other):
x = (self.x*other.x + D*self.y*other.y)%n
y = (self.y*other.x + self.x*other.y)%n
return Point(x, y)
def __mul__(self, d):
Q = Point(1, 0)
P = Point(self.x, self.y)
while d != 0:
if d&1 == 1:
Q += P
P += P
d >>= 1
return Q
def __str__(self) -> str:
return f"{self.x}, {self.y}"
def check_residue(y):
if pow(y, (p - 1)//2, p) == 1 and pow(y, (q - 1)//2, q) == 1:
return True
return False
def gen_point():
while True:
x = getRandomNBitInteger(2000 - 464)
x = bytes_to_long(flag + long_to_bytes(x))
x %= n
y2 = ((x*x - 1)*pow(D, -1, n))%n
if(check_residue(y2)):
yp = pow(y2, (p + 1) // 4, p)
yq = pow(y2, (q + 1) // 4, q)
y = crt([yp, yq], [p, q])
return Point(x, y)
def add(a, b):
if a == "i":
return b
return (D + a*b)*pow(a + b, - 1, n)%n
def power(a, d):
res = "i"
x = a
while d != 0:
if d&1 == 1:
res = add(res, x)
x = add(x, x)
d >>= 1
return res
def point(m):
return Point((m**2 + D)*pow(m**2 - D, -1, n)%n, 2*m*pow(m*m - D, -1, n)%n)
M = gen_point()
Mx, My = M.x, M.y
assert (Mx**2 - D*My**2)%n == 1
e = 65537
C = M*e
print(C)
# 162961013908573567883708515220539578804107270477973090499542519193835498763624042601337274226440312066476160075983577251445943502548471650694617020354363039427231006183897304593798946447482514180041848851245384617847515040075915213698357885114317390276898478740949700799011676589252761736123613456698426984426140183972297018822418150981970598934664464599487393545946613698687046341448558294255407327000026161574779286948527797313848936686929888861150592859573221003557737086661845641459024783317432643308034709718127845066442672512067552552244030535478274512743971354192981490674475749853430371212307520421190, 239668740066200913943562381887193634676899220686058888912170632953311361194017666904277854011894382855202483252661143091091993190645295938873381009873178536800816517615786834926664362950059833369410239281041504946121643304746955139178731148307192034732522723412439705530514113775245607466575056817920259552225402143084439183697819510515790086246564683416312338905722676300264277098153045593619223527605305078928548583405756368607546463429755374790443440435124030514385157787083987202901009878849122637030860266764644062073632184729561756322435322264642199576207018861730005366413597578298926774145872631956206
Bài này tương tự bài trên và cũng có một mạnh thường quân nào đó đã donate factor của \(n\).
Secure Matrix Transmissions¶
from sage.all import *
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import random
import os
import hashlib
from base64 import b64encode, b64decode
FLAG = b'flag{REDACTED}' ## removed the flag
f = open('./intercepted.txt', 'w')
p = 33184772290615481426295675425316668758122179640330548849957081783509
N = 6
gl = GL(N, GF(p))
secret = matrix(gl.random_element())
secret_inv = secret ** (-1)
def encrypt(flag, shared_secret):
i = 0
key = 0
for row in shared_secret:
for item in row:
key += item ** i
i += 1
key = hashlib.sha256(long_to_bytes(int(key))).digest()
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
encrypted_text = cipher.encrypt(pad(flag, AES.block_size))
return b64encode(iv + encrypted_text).decode("utf-8")
def decrypt(cipher, shared_secret):
iv, enc = b64decode(cipher)[:16], b64decode(cipher)[16:]
i = 0
key = 0
for row in shared_secret:
for item in row:
key += item**i
i += 1
key = hashlib.sha256(long_to_bytes(int(key))).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(enc)
return unpad(flag, AES.block_size)
def secure_key_gen():
temp = zero_matrix(GF(p), N)
for i in range(N):
temp[i, i] = random.randint(1, p - 1)
return temp
def gen_params():
A = matrix(gl.random_element())
B = matrix(gl.random_element())
while A.det() == 0 or B.det() == 0:
A = matrix(gl.random_element())
B = matrix(gl.random_element())
f.write(f"A = \n{A}\n") ## intercepted successfully!
f.write(f"B = \n{B}\n") ## intercepted successfully!
return A, B
## generate public parameters
A, B = gen_params()
## for Alice
a = secure_key_gen()
## Sends to Bob
u = secret_inv * A * secret * a * secret_inv * A ** (-1) * secret
f.write(f"u = \n{u}\n") ## intercepted successfully!
## for Bob
b = secure_key_gen()
a_ = secret_inv * A ** (-1) * secret * u * secret_inv * A * secret
key_b = a_ + b
## Sends to Alice
v = secret_inv * B * secret * b * secret_inv * B ** (-1) * secret
f.write(f"v = \n{v}\n") ## intercepted successfully!
## for Alice
b_ = secret_inv * B ** (-1) * secret * v * secret_inv * B * secret
key_a = b_ + a
## Sends to Bob
ct1 = encrypt(b'send me the flag', key_a)
f.write(f"ct1 = {ct1}\n") ## intercepted successfully!
## for Bob
f.write(f"{decrypt(ct1, key_b).decode()}\n")
## Sends to Alice
ct2 = encrypt(FLAG, key_b)
f.write(f"ct2 = {ct2}\n") ## intercepted successfully!
## Read the Flag
# f.write(decrypt(ct2, key_a).decode())
Ở bài này thực hiện trao đổi khóa cho AES. Việc sinh khóa thực hiện như sau:
Sinh một ma trận secret trong \(\mathrm{GL} (6, \mathbb{F}_p)\), đặt là \(S\)
Sinh hai ma trận public \(A\) và \(B\)
Khi đó, Alice tạo khóa bí mật là ma trận chéo \(a\), và tính
\[u = S^{-1} \cdot A \cdot S \cdot a \cdot S^{-1} \cdot A^{-1} \cdot S\]
Tương tự, Bob tạo khóa bí mật là ma trận chéo \(b\), và tính
\[v = S^{-1} \cdot B \cdot S \cdot b \cdot S^{-1} \cdot B^{-1} \cdot S\]
Khóa chung được tính là
\[\begin{split}& S \cdot A^{-1} \cdot S \cdot u \cdot S^{-1} \cdot A \cdot S + b \\ = & S \cdot A^{-1} \cdot S \cdot (S^{-1} \cdot A \cdot S \cdot a \cdot S^{-1} \cdot A^{-1} \cdot S) \cdot S^{-1} \cdot A \cdot S + b \\ = & a + b\end{split}\]
Mình nhận thấy rằng
\[u = (S^{-1} \cdot A \cdot S) \cdot a \cdot (S^{-1} \cdot A \cdot S)^{-1}\]
với \(a\) là ma trận chéo. Như vậy \(a\) là một chéo hóa của \(u\) nên mình chỉ cần chéo hóa \(u\) là tìm được \(a\). Tương tự, chéo hóa \(v\) sẽ tìm được \(b\).
Vấn đề ở đây là việc sắp xếp các trị riêng trên các cột của \(a\). Do đó mình brute tất cả các cách xếp 6 trị riêng của \(u\) lên \(a\). Tương tự cho 6! hoán vị các trị riêng của \(v\) lên \(b\).
from sage.all import *
import hashlib
from Crypto.Cipher import AES
from base64 import b64encode, b64decode
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad, unpad
from itertools import permutations
def encrypt(flag, shared_secret):
i = 0
key = 0
for row in shared_secret:
for item in row:
key += item ** i
i += 1
key = hashlib.sha256(long_to_bytes(int(key))).digest()
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
encrypted_text = cipher.encrypt(pad(flag, AES.block_size))
return b64encode(iv + encrypted_text).decode("utf-8")
def decrypt(cipher, shared_secret):
iv, enc = b64decode(cipher)[:16], b64decode(cipher)[16:]
i = 0
key = 0
for row in shared_secret:
for item in row:
key += item**i
i += 1
key = hashlib.sha256(long_to_bytes(int(key))).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(enc)
#print(flag)
return unpad(flag, AES.block_size)
#return flag
A = [
[29138593503780913754201943837657307143592234072196739580045635829827, 6148431761662606111801006472981115705974813348883936048955056322021, 255190688811745539262654019618923304966823278354790390377834572293, 4635007429840614583671868285931671872308006527885785777738002146955, 820388683419066202292816002168008697348901084338578845510959376989, 8848648700947533848136318240422532714997718007513055917650647852209],
[20131661876369476364264493549146846625866311773479722000539276328885, 10971569230648785536223358100132048040342140912892609767331181671773, 12196400398422566044174421231718572202541358440368513874508701289385, 20777590697412875911127557315404624547865714591197175417771988908211, 18729913520771874874276301881450191669088202274882331954733618873452, 31165493897964991179170526062539442385463582900761104192855946494042],
[19106738337961870383350609153365469961414527306674058101547883507359, 6788814504409465940636915793831407195381283704996994829876327625471, 25092425754137440857520835423049606971603671867355087146670459013365, 22865458707540285908518508716089978575640002471141759113481532584230, 16165751198208920754445225132454666793373453043071285759938056495831, 31647863361110357286878068371524098856651937451812572832095640411942],
[ 2509262555685660513824640006814054289381799717610268653090956954744, 4799808483212483319681248516457786307507844722123460502409435522963, 688030148602238681316815300486805426663924729021026915290782902997, 15212757068125133430071907773077907634928691122626951181124276125724, 28248017570896743821525810663578144681918946912238304895017764923746, 7392202655473070362511755842361409486381502000257816984084532953770],
[ 674060948589374563296532559930663184304751378768469264137758384434, 3381329125334227548623178044938675400703836995274946539226147438123, 26322746669293687716308618078226278052473417739763553212400989662947, 11112080935312197275983357665048225198591108354371073328945968065251, 26784492536660217244414905522283754147708246817664274416015678313954, 2393710578603433780983157725318494164463413897953654493862364144474],
[30121620689521178384747773204718128522467648735672968753722940372545, 24012060216010889890112794166471853505541313396162211702710137419874, 28204404787620956285148056927740515835946630768953280766291692614462, 8390786776266309559204351042106287143828820014522750989935758029389, 5589691711086132346267639936467855365187025764777209120789196218914, 6069061474272034097071030636418398685167426885563338890223076260117]
]
B = [
[26757169742174486353717386573923876136076748056042756860883626304067, 27396434821469610611792944975354242402132304593023079891686914310785, 6250859799132618848444735074839741105337400247540312991892680983053, 27499379409342831097189730195827531709954095934750283472399719363746, 15177260758415632758291783963353722788439655736710809829029982637915, 12184344014690658999789642881581930499761820798837461536407123700085],
[18354247885155640073027169955052745326365388570058713310061622270945, 4614950194446246716509544042928152939656235445482820868703207592235, 815505453872026251293840374522597527509916789080284708676809726137, 5372763283812402396294419433852472897775430144195337424978701545423, 20549812477412976539993173300571502328676998587533521415869840729454, 32671834638183956935772195185420210720686207645862497590534660010084],
[23865783916108799525488829938106323706699349305591133069320361968890, 9008439567345625502625082082739736305599307322047918255988828884102, 1379391441111969735718637046408105000082130587806195986046752893123, 19416370375171524285374545329447056074251138831521552949983610204259, 4858397115363951406096462259699399493285131897740275893002850214494, 9779818636426622153702977753007279465076332549329917100547498834650],
[ 3387329251365848891835333048746797881798374624737031875970941419803, 13898077497927643713190239074927074821900136545851589632217347102717, 30268164061373988274443032891146298085976573352678421224184724566246, 18072427674138919379738507846427248347740392615002353670304549496813, 2392082723406050121177867256658802657939578184986157117857395653150, 31640636517367719806140756835112444409155639128761080279691379301886],
[ 3739989294775377642890322912719312693718746782129575461806663840695, 26892045430886883035578566611572912696810053867158942029322920460223, 7743292688830698450363890781955683502314733158101716202110129331494, 28565513434169769714421607046346478549095943247028582629399157359420, 25501918505284693974653934394656701801605788764168870513066614227035, 12258842850424230103550132955954527470557282426344349654142732774103],
[25001931665375192860709391319367624829795591193433816419985734099454, 17517613590801848895546637558617510647308107968839740063495628045716, 15253185611858394595716250796191777202281383169257250126571416298754, 497048004777611962273982319180934878115509822534520728418791229094, 24947113989306530302945868686731519612247303758417755820534178745896, 9711037028978425250846366443690323714832830881293437780660360769225]
]
u = [
[28879155726567049983454622837721881713004421469649633653126003880251, 22074946600328057026240224251921516029989227864483537878311928528684, 11985344636547053777186855301874485401032363227366605932898421631165, 11038047153398875511855062921770308445072978178537727544345865556069, 17913589562779438181451311229483343663752773108623377725718452883819, 6988548052196701160389870027180255419046432117124570998462066223760],
[12442646139394994295898159421691536460921770233410583384741128805851, 26791343238957883953511341730456926026845067572390616134588257575715, 20044295739622127408570744416765049400182932494144906328843165683951, 3716946288972247122675229801442487271330697050902983897960257015353, 28203806658422488413821254734838742146597120966298092240011671950418, 4762041594051527320517864505450207655232589320366293231953595725863],
[30088717492536940712495821833412730937575223939046572858904284613916, 27041904353687235206996420047457376344449825180129098056224307456338, 24437749819141358658247648214143755332360241994475937257542642573583, 7796437298901905297245658644368499053223939852560146715778064632640, 15614447029063100426172954288407641313530323021423668136405899310194, 8922479681646925758338291598256040373376681973788891756406422763139],
[19322178296033807354940969679463195308540921806504252678149867173138, 33097125072731086770607131468725547500825910975790412321782115869838, 12883750093703623804432147375290510155697961091062129358847651674123, 24597869343287697641622709721671426915780058312255624403180234192713, 26537027184297668426345397663386813121592656652583736980586291216445, 11617206120365401967915791192731000879817682674901777733903856797733],
[16710090447056060108731601191705411717377136736726300253063986063308, 13112164116392985346393033303671764991807289870465207976284880921022, 31389068001989884948885767386697332939461030078718007394707803846255, 29908327338977214304615826417150579857655888232250984362081852839023, 22583975168456327742148140296560922679546031771450762766874213823663, 20255781234412108781956807555843619052915858233204195711555194680279],
[ 8639975336305093270106069074993623126891247360031281653825740040741, 13403900498226599196478196563037659383351290165716358605156795361654, 19127443140313962513371049800518743806366324348931149667137542330176, 1587790520831406950292877253889772565635165863077419349924612463554, 28260643245678615796033409984375030239968039321917236595612922928109, 27245620107342379746895845516019185969531890676595911744377909557532],
]
v = [
[14593469507593520336534893606693100073219081551387449023943771554442, 2283021458111487923710380205365151066104282754263745192237326490551, 13170584523093998223191696419879547969801075848834311698387381471505, 19259980148204759114097202057965316584985415828667111050145931544542, 29885290219184042616179535742918968947354026457415023160998318453828, 15123772566136939254700272466681741447495954560621338927076401710465],
[ 8217862512033149496876384094296269532452490863111766288591338421520, 13729461020836068836298855334139849351346259147300854170266838049852, 11104728330778098008854657250493837339864716593096275438194673593723, 10798384644614928362418932155290042574495162355923347471159291144698, 31877189181091302604647976237742181979760578672930582051196549136046, 1918629350716436456009684853559872579413764560427000121836347921516],
[17260689732862422635435505221480922746751317064535215923993790192886, 15747877220363614821162725299191209258209710570887630567232690904197, 8617228034985901541131740069450254422228498135170302566742947957775, 14253933715820016671570267997896238444667901637428211288460788838246, 16499164346493998999442730191394982099986918128009049722691512093014, 13025912772710188038104092079604197742726564877681113284285303849554],
[ 2573456644853874338239370492651477088261797251129609392543920453838, 32896562598550390417662631073664427877599458467029721692315947839203, 21609625125792777949315379171355985793236349536655762275501735276637, 2064423690239912348059209794358643838603106021323566574579622769345, 10416995935649914543433851087690149206442589809600595549054529630023, 14743736977132006506906381861127077616280508458806441865058344748656],
[ 4225662325959455234970599933733361974460852167061568484358345163405, 10702969665926869787857799410201005975577054702738405546384443139142, 1359255767431309667828876308576650892896838633542052871017414741807, 31671777458706492709787940377250078973397972903701973598970849268174, 24125683246160911728533816896560068159204522435801109506125539244342, 6566591950072749090239378195580530026605442552103644998279546358496],
[ 2340617144223968993993626239720251771746071020532956496851092249201, 18464940637598472739277490361512029859881180718968424684424994902717, 27460971987555371094455429952593747078655439217048574014441041685569, 6667117338244005137290181664972559554258953283885089203943302963181, 20312635823091168798778853401004417385080412291250382174823545520392, 32296141232133239312731746201245526393343079356560448241095997297137],
]
p = 33184772290615481426295675425316668758122179640330548849957081783509
N = 6
ct1 = b't22qVcUY/TYh9hwuASW/6PliQ03dLEWpOTqZHF82rQ/VqmqX7fj2l1YHzX7Cq0Sy'
ct2 = b'8t5wC5gsdXOG7vDvw+uStOT1P2ZhB2FGsr/lvNaBMX+FAZ9aVY4UMOk8neL3KcELjQ3F62aX/sxN4KexO/krK2mm/v10qYrKbLPXljdwvck='
u = matrix(GF(p), u)
v = matrix(GF(p), v)
ea = u.eigenvalues()
eb = v.eigenvalues()
for pa in permutations(range(6)):
for pb in permutations(range(6)):
Ma, Mb = zero_matrix(GF(p), 6), zero_matrix(GF(p), 6)
for i in range(6):
Ma[i, i] = ea[pa[i]]
Mb[i, i] = eb[pb[i]]
key = Ma + Mb
try:
flag = decrypt(ct2, key)
if b'flag' in flag: print(flag)
except:
pass
# b'flag{In53cUr3_K3Y_3xch4ng3_0n_n0n-4b3L14n_gR0up5!!}'
Rebellious¶
from sage.all import *
from Crypto.Util.number import *
import random
import time
random.seed(time.time())
FLAG = b'flag{REDACTED}' ## flag removed
flag = bytes_to_long(FLAG)
f = open('./output.txt', 'w')
p = 2653051169113192956861029164111253541045934291082610203810454254019428617095444726883436858598608538656059147405437762506043477080240989129049112094108099635297397071457202368492446105766960803000479292350528610656494430695078098921185726745996662867511185527654339397
F = GF(p)
a, b = random.randint(2, p), random.randint(2, p)
f.write(f"a = {a}\nb = {b}")
def point_addition(px, py, qx, qy):
rx = F((pow(a, -1, p) * (px * qx - py * qy * (a ** 2) * (pow(b ** 2, - 1, p)))) % p)
ry = F((pow(a, -1, p) * (px * qy + py * qx)) % p)
return (rx, ry)
def scalar_multiplication(px, py, k):
rx = a
ry = 0
while k:
if k % 2:
rx, ry = point_addition(rx, ry, px, py)
px, py = point_addition(px, py, px, py)
k >>= 1
return rx, ry
G = generator_curve() ## implementation hidden for enhancing security
x1 = G[0]
y1 = G[1]
H = scalar(multiplication(x1, y1, flag))
x2 = H[0]
y2 = H[1]
f.write(f"x1 = {x1}\n")
f.write(f"y1 = {y1}\n")
f.write(f"x2 = {x2}\n")
f.write(f"y2 = {y2}\n")
Bài này thuộc dạng discrete logarithm. Với hai điểm \(P = (x_P, y_P)\) và \(Q = (x_Q, y_Q)\), kết quả phép cộng \(R = P + Q\) là
\[x_R = a^{-1} \cdot (x_P \cdot x_Q - y_P \cdot y_Q \cdot a^2 \cdot b^{-2}) \bmod p\]
\[y_R = a^{-1} \cdot (x_P \cdot y_Q + y_P \cdot x_Q) \bmod p\]
Nếu mình viết dưới dạng ma trận thì phép nhân cho kết quả sau:
\[\begin{split}\begin{pmatrix}
x_P & -y_P \cdot a^2 \cdot b^{-2} \\ y_P & x_P
\end{pmatrix} \cdot \begin{pmatrix}
x_Q & -y_Q \cdot a^2 \cdot b^{-2} \\ y_Q & x_Q
\end{pmatrix} = a \begin{pmatrix}
x_R & -y_R \cdot a^2 \cdot b^{-2} \\ y_R & x_R
\end{pmatrix}\end{split}\]
Đề bài tương đương việc giải discrete logarithm
\[\begin{split}a^{k-1} \cdot \begin{pmatrix} x_1 & -y_1 \cdot a^2 \cdot b^{-2} \\ y_1 & x_1 \end{pmatrix}^k = \begin{pmatrix} x_2 & -y_2 \cdot a^2 \cdot b^{-2} \\ y_2 & x_2 \end{pmatrix}\end{split}\]
Đặt \(M = a \cdot \begin{pmatrix} x_1 & -y_1 \cdot a^2 \cdot b^{-2} \\ y_1 & x_1 \end{pmatrix}\),
và \(N = a \cdot \begin{pmatrix} x_2 & -y_2 \cdot a^2 \cdot b^{-2} \\ y_2 & x_2 \end{pmatrix}\) thì việc giải bài toán tương đương với \(M^k = N\).
Mình chéo hóa ma trận \(M = P \cdot D \cdot P^{-1}\). Khi đó \(D^k = P^{-1} \cdot N \cdot P\). Do \(D\) là ma trận chéo nên việc giải bài toán trên tương đương discrete logarithm trên \(\mathrm{GF} (p)\): \(D_{0, 0}^k = (P^{-1} \cdot N \cdot P)_{0, 0} \pmod p\).
from sage.all import *
from Crypto.Util.number import long_to_bytes
p = 2653051169113192956861029164111253541045934291082610203810454254019428617095444726883436858598608538656059147405437762506043477080240989129049112094108099635297397071457202368492446105766960803000479292350528610656494430695078098921185726745996662867511185527654339397
a = 896628675751371304018467516533039804176775933799175745538502687106559694221345569606835023924573486284340033527118135205049330439505968603591951157299842692320540140045548212956876194361589003179447395457270969770617973628611227780145733474250476117969057162498481006
b = 1594141190031606167637964033584529087047496888670585921966214269273813000209103412838275833742634054062344129649888363945908517421292739690476942454492374399040827799113145071785163083279816370591990677345359419792838696359950227158548645341674614589920736730841882901
x1 = 2447311429245810608453598977721926525743937062790274783828355485892913926324404325450262209205021127183454615611616550259333401589502955319014494993678853183049373710785536450442318295835466655474548890496853017541519682383303084185775030215811426581216914216950270956
y1 = 410833649474095008286303725355620198973100699243884756648778973683976772919818182547446663925208006608569743058617356228744003207376383969798498652649980419669823060847067368605737714840647452806304738527797730984565975278507624074132585153613359147658622391652166219
x2 = 1566139005633252473556201451242364632915578424632734493066937660397101401569493967529787221059042873428725135212835566524682514836524110403515558447949858337441010924644644029611890576656944925197135969895065157485428935029723186607110153424152429492883484492551653983
y2 = 2465843379413974191156984954011192642764891821373485281212757233528541318669422125099128501651227153989791786833109663869690960602895820768585534236263284886527281849932400111969526972107723029072948750348496980814617349507385444584704833764454106237879211652308963312
F = GF(p)
class Point0:
def __init__(self, x, y):
self.x = F(x)
self.y = F(y)
def one(self):
return Point0(a, 0)
class Point(Point0):
def __init__(self, x, y):
super().__init__(x, y)
def __str__(self):
return f"{self.x}, {self.y}"
def inverse_element(P):
x1, y1 = P.x, P.y
A = matrix(GF(p), [[x1, -y1*(a**2)*pow(b**2,-1,p)], [y1, x1]])
Q = A.inverse() * vector(GF(p), [a**2, 0])
return Point(Q[0], Q[1])
def point_addition(px, py, qx, qy):
rx = F((pow(a, -1, p) * (px * qx - py * qy * (a ** 2) * (pow(b ** 2, - 1, p)))) % p)
ry = F((pow(a, -1, p) * (px * qy + py * qx)) % p)
return (rx, ry)
def scalar_multiplication(px, py, k):
rx = a
ry = 0
while k:
if k % 2:
rx, ry = point_addition(rx, ry, px, py)
px, py = point_addition(px, py, px, py)
k >>= 1
return rx, ry
M = matrix(GF(p), [[x1, -y1*pow(a,2,p)*pow(b**2,-1,p)], [y1, x1]]) * pow(a, -1, p)
D, P = M.eigenmatrix_right()
N = matrix(GF(p), [[x2, -y2*pow(a,2,p)*pow(b**2,-1,p)], [y2, x2]]) * pow(a, -1, p)
g = D[0][0]
h = (P.inverse() * N * P)[0][0]
t = discrete_log(Mod(h, p), Mod(g, p))
print(long_to_bytes(int(t)))
# b'flag{gR0uP_150M0rPH15m5_4R3_g0NN4_b3_7h3_3nD_0f_y0Ur_L1f3!}'
Secure Matrix Transmissions v2¶
from sage.all import *
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import random
import os
import hashlib
from base64 import b64encode, b64decode
FLAG = b'flag{REDACTED}' ## removed the flag
f = open('./intercepted.txt', 'w')
p = 33184772290615481426295675425316668758122179640330548849957081783509
N = 6
gl = GL(N, GF(p))
def encrypt(flag, shared_secret):
i = 0
key = 0
for row in shared_secret:
for item in row:
key += item ** i
i += 1
key = hashlib.sha256(long_to_bytes(int(key))).digest()
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
encrypted_text = cipher.encrypt(pad(flag, AES.block_size))
return b64encode(iv + encrypted_text).decode("utf-8")
def decrypt(cipher, shared_secret):
iv, enc = b64decode(cipher)[:16], b64decode(cipher)[16:]
i = 0
key = 0
for row in shared_secret:
for item in row:
key += item**i
i += 1
key = hashlib.sha256(long_to_bytes(int(key))).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(enc)
return unpad(flag, AES.block_size)
def gen_params():
a = matrix(gl.random_element())
b = matrix(gl.random_element())
w = matrix(gl.random_element())
while a.det() == 0 or b.det() == 0 or w.det() == 0:
a = matrix(gl.random_element())
b = matrix(gl.random_element())
w = matrix(gl.random_element())
f.write(f"a = \n{a}\n") ## intercepted successfully!
f.write(f"b = \n{b}\n") ## intercepted successfully!
f.write(f"w = \n{w}\n") ## intercepted successfully!
return a, b, w
## generate public parameters
a, b, w = gen_params()
## for Alice
n = random.randint(p // 4, p // 2)
m = random.randint(p // 4, p // 2)
## Sends to Bob
u = a ** n * w * b ** m
f.write(f"u = \n{u}\n") ## intercepted successfully!
## for Bob
r = random.randint(p // 4, p // 2)
s = random.randint(p // 4, p // 2)
## Sends to Alice
v = a ** r * w * b ** s
f.write(f"v = \n{v}\n") ## intercepted successfully!
Ka = a ** n * v * b ** m
Kb = a ** r * u * b ** s
## Sends to Bob
ct1 = encrypt(b'send me the new flag please', Ka)
f.write(f"ct1 = {ct1}\n") ## intercepted successfully!
f.write(f"{decrypt(ct1, Kb).decode()}\n")
## Sends to Alice
ct2 = encrypt(FLAG, Kb)
f.write(f"ct2 = {ct2}\n") ## intercepted successfully!
## Read the Flag
# f.write(decrypt(ct2, Ka).decode())
Bài này mình không giải ra trong CTF. Nhìn lướt qua thì khá giống bài Secure_Matrix_Transmissions ở trên nhưng đời không như mơ :))))
Bài này đề tạo ba ma trận trong \(GL(6, \mathbb{F}_p)\) là \(a\), \(b\) và \(w\).
Alice chọn hai số bí mật \(n\), \(m\) và tính \(a^n \cdot w \cdot b^m\).
Bob chọn hai số bí mật \(r\), \(s\) và tính \(a^r \cdot w \cdot b^s\).
Khóa chung là \(a^{n + r} \cdot w \cdot b^{m + s}\) và được dùng cho AES.
Đối với các bài dạng lũy thừa ma trận thì cách hay được dùng là chéo hóa. Tuy nhiên các ma trận \(a\) và \(b\) không có đủ 6 trị riêng trong \(\mathrm{GF} (p)\). Do đó chúng ta cần mở rộng ra một trường lớn hơn chứa tất cả các trị riêng của \(a\) và \(b\).
Điều này có nghĩa là, ví dụ mình xét đa thức có hệ số thực là \(f(x) = x^2 + 1 = 0\). Các hệ số của \(f(x)\) nằm trong trường \(\mathbb{R}\), tuy nhiên các nghiệm của nó lại nằm trong trường \(\mathbb{C}\) chứa \(\mathbb{R}\).
Tương tự ở bài này, phương trình đặc trưng là một đa thức bậc 6 với hệ số trong \(\mathrm{GF} (p)\). Như vậy các trị riêng của nó phải nằm trong một trường nào đó chứa \(\mathrm{GF} (p)\). Mình chọn \(\mathrm{GF} (p^{10})\) với đa thức tối giản bất kì (nào cũng ra).
Khi đó, mình chéo hóa được \(a = P^{-1} \cdot c \cdot P\) và \(b = Q^{-1} \cdot d \cdot Q\). Thay vào \(u\) mình có
\[u = a^n \cdot w \cdot b^m = P^{-1} \cdot c^n \cdot P \cdot w \cdot Q^{-1} \cdot d^m \cdot Q,\]
tương đương với
\[P \cdot u \cdot Q^{-1} = c^n \cdot (P \cdot w \cdot Q^{-1}) \cdot d^m\]
Đặt \(U = P \cdot u \cdot Q^{-1}\) và \(W = P \cdot w \cdot Q^{-1}\). Nếu mình gọi \(c_0, c_1, \ldots, c_5\) là các trị riêng của \(a\), tương tự \(d_0, d_1, \ldots, d_5\) là các trị riêng của \(b\) thì phương trình trên tương đương:
\[\begin{split}\begin{bmatrix}
c_0^n & & \\
& \ddots & \\
& & c_5^n
\end{bmatrix} \cdot \begin{bmatrix}
W_{00} & & \\
& \ddots & \\
& & W_{55}
\end{bmatrix} \cdot \begin{bmatrix}
d_0^m & & \\
& \ddots & \\
& & d_5^m
\end{bmatrix} = \begin{bmatrix}
U_{00} & & \\
& \ddots & \\
& & U_{55}
\end{bmatrix}\end{split}\]
Mình thấy tương đương rằng \(c_0^n \cdot W_{00} \cdot d_0^m = U_{00}\) và \(c_1^n \cdot W_{10} \cdot d_0^m = U_{10}\). Suy ra
\[\dfrac{c_1^n}{c_0^n} \cdot \dfrac{W_{10}}{W_{00}} = \dfrac{U_{10}}{U_{00}} \pmod p\]
Tổng quát hơn thì
\[\left(\dfrac{c_i}{c_0}\right)^n = \dfrac{U_{i0}}{U_{00}} \cdot \dfrac{W_{00}}{W_{i0}} \pmod p, \quad 1 \leqslant i \leqslant 5\]
Tương tự cho \(d_i\) ta có
\[\left(\dfrac{d_i}{d_0}\right)^m = \dfrac{U_{0i}}{U_{00}} \cdot \dfrac{W_{00}}{W_{0i}} \pmod p, \quad 1 \leqslant i \leqslant 5\]
Như vậy mình có thể tính được \(\left(\dfrac{c_i}{c_0}\right)^n\) và \(\left(\dfrac{d_i}{d_0}\right)^m\). Mình viết lại phép nhân ma trận trên thành:
\[\begin{split}c_0^n \cdot \begin{bmatrix}
1 & & \\
& \ddots & \\
& & (c_5 / c_0)^n
\end{bmatrix} \cdot \begin{bmatrix}
W_{00} & & \\
& \ddots & \\
& & W_{55}
\end{bmatrix} \cdot d_0^m \cdot \begin{bmatrix}
1 & & \\
& \ddots & \\
& & (d_5 / d_0)^m
\end{bmatrix} = \begin{bmatrix}
U_{00} & & \\
& \ddots & \\
& & U_{55}
\end{bmatrix}\end{split}\]
Đặt
\[\begin{split}W_1 = \begin{bmatrix} 1 & & \\ & \ddots & \\ & & (c_5 / c_0)^n \end{bmatrix} \cdot \begin{bmatrix} W_{00} & & \\ & \ddots & \\ & & W_{55} \end{bmatrix} \cdot \begin{bmatrix} 1 & & \\ & \ddots & \\ & & (d_5 / d_0)^m \end{bmatrix}\end{split}\]
thì \(c_0^n \cdot d_0^m \cdot W_1 = U\). Vế trái là số nhân với ma trận, do đó ta có thể lấy bất kì vị trí tương ứng của \(U\) và \(W_1\) để tính \(c_0^n \cdot d_0^m\).
Thực hiện tương tự cho ma trận \(V\) mình cũng tính được \(c_0^r \cdot d_0^s\). Suy ra
\[\begin{split}K = & a^{n+r} \cdot w \cdot b^{m+s} = P^{-1} \cdot c^{n+r} \cdot P \cdot w \cdot Q^{-1} \cdot d^{m+s} \cdot Q \\ = & P^{-1} \cdot c^n \cdot c^r \cdot W \cdot d^m \cdot d^s \cdot Q \\ = & P^{-1} \cdot \begin{bmatrix}
c_0^n & & \\ & \ddots & \\ & & c_5^n
\end{bmatrix} \cdot \begin{bmatrix}
c_0^r & & \\ & \ddots & \\ & & c_5^r
\end{bmatrix} \cdot W \cdot \begin{bmatrix}
d_0^m & & \\ & \ddots & \\ & & d_5^m
\end{bmatrix} \cdot \begin{bmatrix}
d_0^s & & \\ & \ddots & \\ & & d_5^s
\end{bmatrix} \cdot Q \\ = & (c_0^n \cdot d_0^m) \cdot (c_0^r \cdot d_0^s) \cdot P^{-1} \cdot \begin{bmatrix}
1 & & \\ & \ddots & \\ & & (c_5 / c_0)^n
\end{bmatrix} \cdot \begin{bmatrix}
1 & & \\ & \ddots & \\ & & (c_5 / c_0)^r
\end{bmatrix} \cdot W \\ & \cdot \begin{bmatrix}
1 & & \\ & \ddots & \\ & & (d_5 / d_0)^m
\end{bmatrix} \cdot \begin{bmatrix}
1 & & \\ & \ddots & \\ & & (d_5 / d_0)^s
\end{bmatrix} \cdot Q\end{split}\]
Ở đây mình có thể tính tất cả thành phần \(c_0^n \cdot d_0^m\), \(c_0^r \cdot d_0^s\), và các ma trận. Từ đó mình có thể tìm được ma trận \(K\) và dùng nó để lấy flag.
from sage.all import *
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import random
import os
import hashlib
from base64 import b64encode, b64decode
a = [
[ 7438990672506171962229953039732043872296133243241284337757143437971, 5908789919315683911934002246711242097556001082151324070510964188629, 821377081169549532467637447596076223210515297635890901086729923313, 8803689112821400567694559031419901653192500860623106299971487002773, 18612975347222062032390601729988488582163325285065232353911648213496, 28406415395368061679599027919943782204930529636321409910366075254914],
[23030339234031276552371460849096733391956507787097942340730822567899, 2806456362262124176231332899673279143879149767093309750789173579717, 2444120197523056286205749542083088031942425729246534842180679293051, 31777746489654830141280110796153336536456891579494976087750480508881, 3135461709604734633174324618217609786257832886969827761799685700297, 29150213556275906428737094372415762776161562249515931809149160979462],
[17811710321991401418887384477112708777554347967312167056231822486458, 16175313598271410645419867063704440051893872039312165918491849609121, 19484833575660036922281798450151761251888042554456008122738616237566, 6399339063832623132521066566841418341729515675888662370492430783512, 32965756883728415906453172612933516889443811185419762074179164197728, 26876920919574460425312516480761305560419145040867232436335341953931],
[18905938652965757389709522711431812720190470549742246985133281958758, 32355951097020136622658259135740028542772526287257507861244879064817, 8143637413177425637015808154683571140099612302407020234581109069110, 19274081905556571775557401722206326587273549654982963263472874753802, 14188658485813422062092019037545772668846235395461712812728980165020, 22973887769825410115039966130871385101721034893851588644148685171118],
[ 8473072721257615774000050308147501686186073487086093683583266181724, 13069883091043208795866763417001102148029265509467886681527508108227, 13530815665496399596157710302278067669875493954517875213334772494833, 10314149807801648638906376954505943768175798470740399817688240276874, 32602590761001163511262244048393203814390811262617195391214856647890, 1161448068427194445811211261400583586216441930662530767647750729665],
[ 4467634017288682281421958504154578275978833389408289917124074837899, 28546689158470334794048601179899962710541946133058819131918760633104, 14468488515420984908853379737404308268486935702415965466876669344726, 1576767666491546576252216760489732106458594422859764943774505646047, 14539000020238279379455275218209775254729503530578118336000433590507, 17033683389583212080938445996925287749776048537941321065191592969420],
]
b = [
[29138593503780913754201943837657307143592234072196739580045635829827, 6148431761662606111801006472981115705974813348883936048955056322021, 255190688811745539262654019618923304966823278354790390377834572293, 4635007429840614583671868285931671872308006527885785777738002146955, 820388683419066202292816002168008697348901084338578845510959376989, 8848648700947533848136318240422532714997718007513055917650647852209],
[20131661876369476364264493549146846625866311773479722000539276328885, 10971569230648785536223358100132048040342140912892609767331181671773, 12196400398422566044174421231718572202541358440368513874508701289385, 20777590697412875911127557315404624547865714591197175417771988908211, 18729913520771874874276301881450191669088202274882331954733618873452, 31165493897964991179170526062539442385463582900761104192855946494042],
[19106738337961870383350609153365469961414527306674058101547883507359, 6788814504409465940636915793831407195381283704996994829876327625471, 25092425754137440857520835423049606971603671867355087146670459013365, 22865458707540285908518508716089978575640002471141759113481532584230, 16165751198208920754445225132454666793373453043071285759938056495831, 31647863361110357286878068371524098856651937451812572832095640411942],
[ 2509262555685660513824640006814054289381799717610268653090956954744, 4799808483212483319681248516457786307507844722123460502409435522963, 688030148602238681316815300486805426663924729021026915290782902997, 15212757068125133430071907773077907634928691122626951181124276125724, 28248017570896743821525810663578144681918946912238304895017764923746, 7392202655473070362511755842361409486381502000257816984084532953770],
[ 674060948589374563296532559930663184304751378768469264137758384434, 3381329125334227548623178044938675400703836995274946539226147438123, 26322746669293687716308618078226278052473417739763553212400989662947, 11112080935312197275983357665048225198591108354371073328945968065251, 26784492536660217244414905522283754147708246817664274416015678313954, 2393710578603433780983157725318494164463413897953654493862364144474],
[30121620689521178384747773204718128522467648735672968753722940372545, 24012060216010889890112794166471853505541313396162211702710137419874, 28204404787620956285148056927740515835946630768953280766291692614462, 8390786776266309559204351042106287143828820014522750989935758029389, 5589691711086132346267639936467855365187025764777209120789196218914, 6069061474272034097071030636418398685167426885563338890223076260117],
]
w = [
[26757169742174486353717386573923876136076748056042756860883626304067, 27396434821469610611792944975354242402132304593023079891686914310785, 6250859799132618848444735074839741105337400247540312991892680983053, 27499379409342831097189730195827531709954095934750283472399719363746, 15177260758415632758291783963353722788439655736710809829029982637915, 12184344014690658999789642881581930499761820798837461536407123700085],
[18354247885155640073027169955052745326365388570058713310061622270945, 4614950194446246716509544042928152939656235445482820868703207592235, 815505453872026251293840374522597527509916789080284708676809726137, 5372763283812402396294419433852472897775430144195337424978701545423, 20549812477412976539993173300571502328676998587533521415869840729454, 32671834638183956935772195185420210720686207645862497590534660010084],
[23865783916108799525488829938106323706699349305591133069320361968890, 9008439567345625502625082082739736305599307322047918255988828884102, 1379391441111969735718637046408105000082130587806195986046752893123, 19416370375171524285374545329447056074251138831521552949983610204259, 4858397115363951406096462259699399493285131897740275893002850214494, 9779818636426622153702977753007279465076332549329917100547498834650],
[ 3387329251365848891835333048746797881798374624737031875970941419803, 13898077497927643713190239074927074821900136545851589632217347102717, 30268164061373988274443032891146298085976573352678421224184724566246, 18072427674138919379738507846427248347740392615002353670304549496813, 2392082723406050121177867256658802657939578184986157117857395653150, 31640636517367719806140756835112444409155639128761080279691379301886],
[ 3739989294775377642890322912719312693718746782129575461806663840695, 26892045430886883035578566611572912696810053867158942029322920460223, 7743292688830698450363890781955683502314733158101716202110129331494, 28565513434169769714421607046346478549095943247028582629399157359420, 25501918505284693974653934394656701801605788764168870513066614227035, 12258842850424230103550132955954527470557282426344349654142732774103],
[25001931665375192860709391319367624829795591193433816419985734099454, 17517613590801848895546637558617510647308107968839740063495628045716, 15253185611858394595716250796191777202281383169257250126571416298754, 497048004777611962273982319180934878115509822534520728418791229094, 24947113989306530302945868686731519612247303758417755820534178745896, 9711037028978425250846366443690323714832830881293437780660360769225],
]
u = [
[ 5825031659324706050484801105302316168711627549976428741897565778238, 26579579313304090280374759901936570473112775514477148512050158028288, 14849608183427960446105822837793476094045414621076547965499725889502, 11979273625858866517057813239005684881673705761324764205014117722392, 26025122632360852670365522093494325590850705092310892191715955717364, 32528404210791786666457681251229140412311477527356466616849680617888],
[29806478330383930819765275373453293353268788984674965955397131283555, 9996348607632108030887699427448697808963817912783158665797621137584, 19111427024250653014004242198161419643570798030361216643047350320346, 25114851322722222620572657745776477417800433075526471329546553064518, 25704701458784823510688396958645545324984922088239828625340538227428, 8137730546021885209024274977161006334738370571726015849690803176439],
[27950251470703760135283216843276089541967801496460674575327852649078, 29951116004224090374793891295687000359982339153087934106020231352800, 13182808359361308543751345557412962779136237222958383283193564721632, 22896310354916948415008572754187001942632163398092386550203180731696, 2500374894549186486836740304615695649842153757315963985885278471931, 7660182027041496767042401344918187841441577406449050610357454824064],
[ 7127619543606793156237716103397674314161383119780608184367362102613, 17463127937282737114673044662782016721025748002532115924036546780641, 590562582706667090827299215464277730608726547482746581408576786643, 4305120985454270499588734613862610197760307880816806992997837045739, 6835525256546309205694851761742070611006670609996351947755921232528, 10318987224820532670694144750368695454879310172571313238990880680675],
[ 8525028929820531155322183772058156119160524557050768370709442240435, 6672716478991472233762934335338429221013158128309667775608335597924, 21465370433871927244370086539100619997974201975399673096489162607625, 13357121187594162869537660449807309300666550288146980789439552257529, 29370932025449389468104931463756190832226696259884456676808952343576, 30532037850547858724719904031667663113800819526101990847502946242801],
[22586288472033951548944237678778945513920160294547505168871778139615, 10519109481860319161116486685520175117387605352307420625811998166425, 30588064229218340477575072156889954843376151521459928097718789969128, 92249473545709104888052690080695945346613394952019162513448532626, 12787341925267835156312786362013310735712745036605794360987990859522, 8068914179463051083376769021851690750502973562451753222090591856573],
]
v = [
[ 6473807763954025094626776056817991272217357613624866350048622300058, 18367099405182942062341317505191432538800640634215210777119820011410, 5658332488521402896699124692832013919796056230329072063014923897249, 2386928190063795878057832083026051219211587102804465375264593086583, 15120067361124597048277981720825507789301577783318649008930871911106, 5961343374029284819371036280753253922332080488529181991336810089499],
[ 5803049456689071734447632321404722566263637825980694048184902888798, 5713306790304507636239520933996689204171974549946008452467152281026, 563433073530161914724713826045638260639291103088834185973129549229, 2823082366839787358254599688882406830532599516831966755347921238868, 8854767430679224484596212415170696013256523848033801848164764299136, 9984086565520078604490883311962904775971921002260140461326472679196],
[14617641572277125928050023989988572261152889574781581704275482369135, 1226216237263987138692416266849267833729712985049479382126779642933, 18173701696533623379052887299164052458694499320013175469495175685384, 16526975008694759098940799256932805310390991267176320186869174350913, 8821666907756499755106011350171481357097998917671744174181651049380, 30952916903073018399936118678342178696586609409709878807250803298997],
[30119753366470674691925611645102032301779365451101274022734428178416, 15863627019086043190556098182012756864510537358087129177256252460187, 1252335627851220318425788900689243212286296979508964762563173067073, 29557410854963822176726804657904177560684724219459654009660305817932, 27847239983629862342370790780847271943330535969640063277161854216436, 32991653750281149949256604166057428808837292331367624819545956900804],
[12146112493117699840663396677451027748690599368816766805866161877005, 7934805063472727931762305702723099791089878885183522829543436178106, 15821087262497766800858978929185984304100604192170884522095916806044, 3484738244945243188710186645005712582534561735085941129531319415537, 21626751177056341710153918532520481575567986720285508844104080304590, 15542821705899612161574593236479670002254054344467277573227576227340],
[ 6810813497623829421400688703982617561368366037988617003294242571984, 16800519968366018241100592879555379422939404231119370074929695554292, 1771748302639288098172091724479816619811968138679637319227473595560, 4600048895720597997559508932637340595186751708740069828831676222774, 9580966624991191962937365186685046106282166330935481780660725313276, 5270134497900285355093141717326343873520107670209270084558443553896],
]
ct1 = "E9I4ZKpv8QNPF/btCNYDmMwRxcHCwnBA05bvNB6xP2SElWP6lvyr8NKONYdVe8/h"
ct2 = "/PLzQibJlnw0CXQkeYEMwHJG3gjoOfEqF/cjLcSnIKB2oIwYqZ1R9Ro2XtE4R+g5nGEUqygGsxal7nYcqbjlMA=="
p = 33184772290615481426295675425316668758122179640330548849957081783509
N = 6
gl = GL(N, GF(p))
def encrypt(flag, shared_secret):
i = 0
key = 0
for row in shared_secret:
for item in row:
key += item ** i
i += 1
key = hashlib.sha256(long_to_bytes(int(key))).digest()
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
encrypted_text = cipher.encrypt(pad(flag, AES.block_size))
return b64encode(iv + encrypted_text).decode("utf-8")
def decrypt(cipher, shared_secret):
iv, enc = b64decode(cipher)[:16], b64decode(cipher)[16:]
i = 0
key = 0
for row in shared_secret:
for item in row:
key += item**i
i += 1
key = hashlib.sha256(long_to_bytes(int(key))).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(enc)
return unpad(flag, AES.block_size)
F = GF(p)['x']
x = F.gen()
modulus = x**10 + 12444475755660643828750965026220924558409341527436991900309741576131*x**3 + 23991673485386167035017875302974089550359772818867167580641435225643*x**2 + 33004383022948339382298131535224305232104092670530634187076470305806*x + 10431397437307386265522604278233367493067750077888865627627781691508
F10 = GF(p**10, name='a', modulus=modulus)
a, b, w = matrix(F10, a), matrix(F10, b), matrix(F10, w)
u, v = matrix(F10, u), matrix(F10, v)
c, P = a.eigenmatrix_left()
d, Q = b.eigenmatrix_left()
W = P * w * Q.inverse()
U = P * u * Q.inverse()
V = P * v * Q.inverse()
ck = [1]
dk = [1]
for i in range(1, 6):
ck.append((W[0, 0] / W[i, 0]) * (U[i, 0] / U[0, 0]))
dk.append((W[0, 0] / W[0, i]) * (U[0, i] / U[0, 0]))
W1 = diagonal_matrix(F10, ck) * W * diagonal_matrix(F10, dk)
ck_ = [1]
dk_ = [1]
for i in range(1, 6):
ck_.append((W[0, 0] / W[i, 0]) * (V[i, 0] / V[0, 0]))
dk_.append((W[0, 0] / W[0, i]) * (V[0, i] / V[0, 0]))
W2 = diagonal_matrix(ck_) * W * diagonal_matrix(dk_)
cndm = U[0, 0] / W1[0, 0]
assert U == cndm * W1
crds = V[0, 0] / W2[0, 0]
K = cndm * crds * P.inverse() * diagonal_matrix(ck) * diagonal_matrix(ck_) * W * diagonal_matrix(dk_) * diagonal_matrix(dk) * Q
print(decrypt(ct2, K))
# b'flag{In53cUr3_n0n-4b3L14n_d1Ff13_H31Lm4N!}'