Backdoor CTF 2023 ***************** PRSA ==== .. only:: html .. code-block:: python 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. = PolynomialRing(GF(2), x) p, q = [F.irreducible_element(random.randint(2 ** 10, 2 ** 12)) for _ in range(2)] R. = 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 :math:`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 :math:`n(x) \bmod{p(x) \cdot q(x)}`. Ciphertext khi đó là :math:`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 :math:`d_p = \deg p(x)` thì số phần tử khác 0 trong :math:`\mathrm{GF} (2^{d_p})` là :math:`2^{d_p} - 1`. Tương tự cho :math:`q(x)` số phần tử khác :math:`0` là :math:`2^{d_q} - 1`. Do đó mình tính nghịch đảo của :math:`e = 2^{256}` trong modulus :math:`(2^{d_p} - 1) \cdot (2^{d_q} - 1)`. .. only:: html .. code-block:: python from Crypto.Util.number import long_to_bytes e = 115792089237316195423570985008687907853269984665640564039457584007913129639936 F. = 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. = 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 ======== .. only:: html .. code-block:: python 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<>= 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 :math:`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 :math:`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 :math:`P = (x_P, y_P)` và :math:`Q = (x_Q, y_Q)` là tọa độ điểm :math:`P` và :math:`Q`. Khi đó phép cộng :math:`R = P + Q` là: .. math:: x_R = x_P \cdot x_Q + D \cdot y_P \cdot y_Q \bmod n .. math:: 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: .. math:: \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} Khi đó mình ghi lại ma trận :math:`M = \begin{pmatrix} x & D \cdot y \\ y & x \end{pmatrix}` và ciphertext là :math:`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 :math:`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à :math:`(p+1) \cdot (q+1)` nên ta chỉ cần tính :math:`d = e^{-1} \bmod{(p+1) \cdot (q+1)}` và :math:`M = C^d`. Flag là tọa độ :math:`x` của :math:`M`. .. only:: html .. code-block:: python 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\xb7tZ\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 ================ .. only:: html .. code-block:: python 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 :math:`n`. Secure Matrix Transmissions =========================== .. only:: html .. code-block:: python 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 :math:`\mathrm{GL} (6, \mathbb{F}_p)`, đặt là :math:`S` - Sinh hai ma trận public :math:`A` và :math:`B` Khi đó, Alice tạo khóa bí mật là ma trận chéo :math:`a`, và tính .. math:: 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 :math:`b`, và tính .. math:: v = S^{-1} \cdot B \cdot S \cdot b \cdot S^{-1} \cdot B^{-1} \cdot S Khóa chung được tính là .. math:: & 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 Mình nhận thấy rằng .. math:: u = (S^{-1} \cdot A \cdot S) \cdot a \cdot (S^{-1} \cdot A \cdot S)^{-1} với :math:`a` là ma trận chéo. Như vậy :math:`a` là một chéo hóa của :math:`u` nên mình chỉ cần chéo hóa :math:`u` là tìm được :math:`a`. Tương tự, chéo hóa :math:`v` sẽ tìm được :math:`b`. Vấn đề ở đây là việc sắp xếp các trị riêng trên các cột của :math:`a`. Do đó mình brute tất cả các cách xếp 6 trị riêng của :math:`u` lên :math:`a`. Tương tự cho 6! hoán vị các trị riêng của :math:`v` lên :math:`b`. .. only:: html .. code-block:: python 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 ========== .. only:: html .. code-block:: python 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 :math:`P = (x_P, y_P)` và :math:`Q = (x_Q, y_Q)`, kết quả phép cộng :math:`R = P + Q` là .. math:: x_R = a^{-1} \cdot (x_P \cdot x_Q - y_P \cdot y_Q \cdot a^2 \cdot b^{-2}) \bmod p .. math:: 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: .. math:: \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} Đề bài tương đương việc giải discrete logarithm .. math:: 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} Đặt :math:`M = a \cdot \begin{pmatrix} x_1 & -y_1 \cdot a^2 \cdot b^{-2} \\ y_1 & x_1 \end{pmatrix}`, và :math:`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 :math:`M^k = N`. Mình chéo hóa ma trận :math:`M = P \cdot D \cdot P^{-1}`. Khi đó :math:`D^k = P^{-1} \cdot N \cdot P`. Do :math:`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 :math:`\mathrm{GF} (p)`: :math:`D_{0, 0}^k = (P^{-1} \cdot N \cdot P)_{0, 0} \pmod p`. .. only:: html .. code-block:: python 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 ============================== .. only:: html .. code-block:: python 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 :math:`GL(6, \mathbb{F}_p)` là :math:`a`, :math:`b` và :math:`w`. Alice chọn hai số bí mật :math:`n`, :math:`m` và tính :math:`a^n \cdot w \cdot b^m`. Bob chọn hai số bí mật :math:`r`, :math:`s` và tính :math:`a^r \cdot w \cdot b^s`. Khóa chung là :math:`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 :math:`a` và :math:`b` không có đủ 6 trị riêng trong :math:`\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 :math:`a` và :math:`b`. Điều này có nghĩa là, ví dụ mình xét đa thức có hệ số thực là :math:`f(x) = x^2 + 1 = 0`. Các hệ số của :math:`f(x)` nằm trong trường :math:`\mathbb{R}`, tuy nhiên các nghiệm của nó lại nằm trong trường :math:`\mathbb{C}` chứa :math:`\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 :math:`\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 :math:`\mathrm{GF} (p)`. Mình chọn :math:`\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 :math:`a = P^{-1} \cdot c \cdot P` và :math:`b = Q^{-1} \cdot d \cdot Q`. Thay vào :math:`u` mình có .. math:: 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 .. math:: P \cdot u \cdot Q^{-1} = c^n \cdot (P \cdot w \cdot Q^{-1}) \cdot d^m Đặt :math:`U = P \cdot u \cdot Q^{-1}` và :math:`W = P \cdot w \cdot Q^{-1}`. Nếu mình gọi :math:`c_0, c_1, \ldots, c_5` là các trị riêng của :math:`a`, tương tự :math:`d_0, d_1, \ldots, d_5` là các trị riêng của :math:`b` thì phương trình trên tương đương: .. math:: \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} Mình thấy tương đương rằng :math:`c_0^n \cdot W_{00} \cdot d_0^m = U_{00}` và :math:`c_1^n \cdot W_{10} \cdot d_0^m = U_{10}`. Suy ra .. math:: \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ì .. math:: \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 :math:`d_i` ta có .. math:: \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 :math:`\left(\dfrac{c_i}{c_0}\right)^n` và :math:`\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: .. math:: 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} Đặt .. math:: 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} thì :math:`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 :math:`U` và :math:`W_1` để tính :math:`c_0^n \cdot d_0^m`. Thực hiện tương tự cho ma trận :math:`V` mình cũng tính được :math:`c_0^r \cdot d_0^s`. Suy ra .. math:: 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 Ở đây mình có thể tính tất cả thành phần :math:`c_0^n \cdot d_0^m`, :math:`c_0^r \cdot d_0^s`, và các ma trận. Từ đó mình có thể tìm được ma trận :math:`K` và dùng nó để lấy flag. .. only:: html .. code-block:: python 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!}'