BackdoorCTF 2023 writeups
Something_in_Common
m^e can be solved with the chinese remainder theorem.
\[m^e \equiv c_1 \ \text{(mod } n_1 \text{)}\] \[m^e \equiv c_2 \ \text{(mod } n_2 \text{)}\] \[m^e \equiv c_3 \ \text{(mod } n_3 \text{)}\] \[\text{...}\]Then take the eth root to get m.
from Crypto.Util.number import long_to_bytes
from sympy.ntheory.modular import crt
from sympy import cbrt
ns = [231689896592553079225008346159565141292942746185614335113030628126523977770897610833,7171431858055720778675521,66926822362327139196541990168817936306935699,437335592290538364420374052921942150635299817629860400585996176158735283605573507708521,289641633885807692370107575915133663791,667489211907833441904090408183964916738111,3567528272153764003837574317682649383619949327607]
cs = [70932244057518414814271820586538428333420562252483260602196856595136636875881109254,6776581747370220150625940,48565469191356626147008517582743644359421796,8794419984130129081066440741470891653922464557881503503363167507918405790466608773101,172864555741817549854149625512946760571,123698332225047871848637413013333477895868,2621823962661199268500092259451160990545103771980,]
print(long_to_bytes(cbrt(crt(ns, cs)[0])))
# flag{Wh4t_d0_y0u_m34n_1t_h4s_t0_b3_co-pr1m3}
mini_RSA
m^3 < n so we can take normal cube root of c.
from Crypto.Util.number import long_to_bytes
from sympy import cbrt
c = 5926440800047066468184992240057621921188346083131741617482777221394411358243130401052973132050605103035491365016082149869814064434831123043357292949645845605278066636109516907741970960547141266810284132826982396956610111589
print(long_to_bytes(cbrt(c)))
# flag{S0_y0u_c4n_s0lv3_s0m3_RSA}
mini_RSA_v2
Looking at the challenge code:
def check(p, q, n):
a_ = random.randint(1, 100)
b_ = random.randint(1, 100)
s = fast_exp(p, fast_exp(q, a_, (p - 1) * (q - 1)), n)
t = fast_exp(q, fast_exp(p, b_, (p - 1) * (q - 1)), n)
result = s + t
print(result)
Now we can actually prove that s=p and similarly t=q:
from Crypto.Util.number import getPrime
from random import randint
p = getPrime(256)
q = getPrime(256)
n = p*q
phi = (p-1)*(q-1)
a = randint(1, 100)
# proving this:
assert p == pow(p, pow(q, a, phi), n)
# rewrite q^a mod phi as q^a + k*(q-1) for some k
k = (pow(q, a, phi) - q**a) // (q-1)
assert p == pow(p, q**a + k*(q-1), n)
# to show this is true mod n we can show it's true mod p and mod q
assert p % p == pow(p, q**a + k*(q-1), p)
assert p % q == pow(p, q**a + k*(q-1), q)
# case mod p:
# trivial, 0 = p^x mod p
# case mod q:
assert p % q == (pow(p, q**a, q) * pow(p, k*(q-1), q)) % q # expand exponents
assert p % q == (pow(p, q**a, q) * pow(pow(p, k, q), q-1, q)) % q # p^(k*(q-1)) = (p^k)^(q-1)
assert p % q == pow(p, q**a, q) % q # fermat's little theorem x^(q-1) ≡ 1 (mod q)
"""
Now we use an extension of fermat's little theorem
which can be proved by induction
x^(q^a) ≡ x (mod q)
base case a=1:
x^(q^1) ≡ x^q ≡ x (mod q)
inductive case a=k+1:
x^(q^(k+1)) ≡ x^(q^k * q) ≡ (x^(q^k))^q ≡ x^(q^k) (mod q)
subbing in our inductive assumption x ≡ x^(q^k):
(x^(q^k))^q ≡ x^q ≡ x (mod q)
so by induction x^(q^a) ≡ x (mod q) for all x
"""
Therefore the hint given, s+t, is p+q, which we can use to find phi:
phi = (p-1) * (q-1) = p*q - p - q + 1 = n - (p+q) + 1
from Crypto.Util.number import long_to_bytes
st = 19238118289292540845900132045328657353776835000175884072088390761517035980189490490459144989703825736320337279576084998885094661611740596902279433080118842
c = 8706151122704717355844546946300718218661297718003809762659247903847434328687915436733170976217817899448539289359073472514594584336897461146424215943312922513357040989774130659844482065845748436287563176648482538678604968897565248411495214863860346421741054695295323750935794123435244378357713784569300292101
n = 91006417473818125376038413443680810078297391307262694881962992972007772034646331080442026536488576075677538183326514650683359389396367200966050480101000687177953951819685597201494449347363819516742644021041231090322946128861477233797216337306770224218011823327837033401012386386102401543925525885359433574841
phi = n - st + 1
d = pow(65537, -1, phi)
print(long_to_bytes(pow(c, d, n)))
# flag{I_4m_5tuck_0n_Th3_pl4n3t_Eg0_s4ve_M3}
PRSA
from Crypto.Util.number import long_to_bytes
F.<x> = PolynomialRing(GF(2))
pq = 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 = factor(pq)
p, q = p[0], q[0]
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
phi = (2**max(p.dict().keys()) - 1) * (2**max(q.dict().keys()) - 1)
e = 2 ** 256
n = c ^ pow(e, -1, phi)
flag = long_to_bytes(sum(2**i for i in n._polynomial.dict().keys()))
print(flag)
# flag{S0_1mPL3m3n71nG_R54_0n_P0lYn0m1aL5_1n5734d_d1dn7_w0rk_hUh!!?}
Knapsack
from itertools import combinations
from Crypto.Cipher import AES
import hashlib
from tqdm import tqdm
from Crypto.Util.number import *
def solve_subset(arr_, s, brute):
for arr in tqdm(combinations(arr_, len(arr_) - brute)):
N = ceil(sqrt(len(arr)) / 2)
M = identity_matrix(QQ, len(arr))
M = M.augment(N*vector(arr))
M = M.stack(vector([-1/2 for _ in range(len(arr))] + [-N*s]))
for row in M.LLL():
for row in (row, -row):
kk = [i+1/2 for i in row][:-1]
if not all([i in (0, 1) for i in kk]):
continue
subset = [xx for xx, k in zip(arr, kk) if k]
if sum(subset) == s:
return subset
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
brute = 1 # lmao
subset = solve_subset(arr_, s, brute)
secret = 0
for i, x in enumerate(arr_):
if x in subset:
secret += 2**i
secret = long_to_bytes(secret)
ct = bytes.fromhex('af95a58f4fbab33cd98f2bfcdcd19a101c04232ac6e8f7e9b705b942be9707b66ac0e62ed38f14046d1cd86b133ebda9')
key = hashlib.sha256(secret).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
print(cipher.decrypt(ct))
# flag{N0t_r34dy_f0r_M3rkl3-H3llman}
Solving subset sum problem with LLL:
First write out the equation as:
sum = arr_0 * b_0 + arr_1 * b_1 + arr_2 * b_2 + ... + arr_i * b_i
where all b_i are either 0 or 1.
Now we can write with vectors (I’ll just do an example with array of length 4):
The vectors on the LHS form our lattice basis:
[1, 0, 0, 0, arr_0]
[0, 1, 0, 0, arr_1]
[0, 0, 1, 0, arr_2]
[0, 0, 0, 1, arr_3]
[0, 0, 0, 0, -s ]
Then when we reduce it with LLL we (hopefully) get
one of the rows as the RHS vector (b0, b1, b2, b3, 0):
from random import randint
arr = [ randint(1,1000000000000) for _ in range(4) ]
s = sum([i for i in arr if randint(0, 1) == 0])
M = Matrix([
[1, 0, 0, 0, arr[0]],
[0, 1, 0, 0, arr[1]],
[0, 0, 1, 0, arr[2]],
[0, 0, 0, 1, arr[3]],
[0, 0, 0, 0, -s ],
])
for row in M.LLL():
if row[-1] == 0:
print(row)
subset = [arr[i] for i, x in enumerate(row[:-1]) if x==1]
print(sum(subset) == s)
Now, an improvement we can make to our basis is to include our guesses for what all b_i are.
Since they’re either 0 or 1 we’ll take the average, 1/2. Our vector equation looks like this:
This time our target vector has b_i - 1/2 so we have to add 1/2 to get b_i.
[1 , 0 , 0 , 0 , arr_0]
[0 , 1 , 0 , 0 , arr_1]
[0 , 0 , 1 , 0 , arr_2]
[0 , 0 , 0 , 1 , arr_3]
[-1/2, -1/2, -1/2, -1/2, -s]
Let’s run a test to see how much better the improved basis is versus the previous basis:
from random import randint
def previous_basis(length):
arr = [ randint(1,1000000000000) for _ in range(length) ]
s = sum([i for i in arr if randint(0, 1) == 0])
M = identity_matrix(len(arr))
M = M.augment(vector(arr))
M = M.stack(vector([0 for _ in range(len(arr))] + [-s]))
for row in M.LLL():
for row in (row, -row):
if row[-1] == 0:
subset = [arr[i] for i, x in enumerate(row[:-1]) if x==1]
if sum(subset) == s:
return True
return False
def improved_basis(length):
arr = [ randint(1,1000000000000) for _ in range(length) ]
s = sum([i for i in arr if randint(0, 1) == 0])
M = identity_matrix(QQ, len(arr))
M = M.augment(vector(arr))
M = M.stack(vector([-1/2 for _ in range(len(arr))] + [-s]))
for row in M.LLL():
for row in (row, -row):
if row[-1] == 0:
subset = [arr[i] for i, x in enumerate(row[:-1]) if x+1/2==1]
if sum(subset) == s:
return True
return False
def test(f, length):
n = 100
count = 0
for _ in range(n):
if f(length):
count += 1
return f'{float(count/n):.2%}'
for length in range(10, 40):
print(f"{length = }:")
print("prev", test(previous_basis, length))
print("impr", test(improved_basis, length))
print()
By length 30 the previous one has fallen to ~25% success whilst the improved is still at ~95%!
Not bad :)
Curvy_Curves
First time seeing William’s p+1 factorisation in a CTF!
This script factors n for this challenge and also the next revenge ‘Safe Curvy Curve’:
from math import isqrt, gcd
from gmpy2 import next_prime
def mlucas(v, a, n):
v1, v2 = v, (v**2 - 2) % n
for bit in bin(a)[3:]:
if bit == "0":
v1, v2 = (v1**2 - 2) % n, (v1*v2 - v) % n
else:
v1, v2 = (v1*v2 - v) % n, (v2**2 - 2) % n
return v1
def ilog(x, b):
l = 0
while x >= b:
x //= b
l += 1
return l
def factor(n):
v = 0
while True:
v += 1
p = 1
while True:
p = next_prime(p)
e = ilog(isqrt(n), p)
if e == 0:
break
for _ in range(e):
v = mlucas(v, p, n)
g = gcd(v - 2, n)
if 1 < g < n:
return g
if g == n:
break
if p > 500000:
break
n1 = 22409692526386997228129877156813506752754387447752717527887987964559571432427892983480051412477389130668335262274931995291504411262883294295070539542625671556700675266826067588284189832712291138415510613208544808040871773692292843299067831286462494693987261585149330989738677007709580904907799587705949221601393
n2 = 325325755182481058670589439237195225483797901549838835146388756505962515992731682902174843378473793118013824587686743801443229435097379024643408429957717590072275498734396840489261986361764935791083084431387935565119970246214821662977047205360090509590387268197591520307878877103247121412898793371812283196864079961633428662039795223806526580626911586062085681619829271800589543048515261459541945856915535056363750996243146294104205192635607675773145823355324367791593757860302117944097894321078809559514655550115178790472355420484756646090492860950760854985816746318432545157312928351659730275368368710393481
print(factor(n1))
print(factor(n2))
from Crypto.Util.number import *
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}"
D = 136449572493235894105040063345648963382768741227829225155873529439788000141924302071247144068377223170502438469323595278711906213653227972959011573520003821372215616761555719247287249928879121278574549473346526897917771460153933981713383608662604675157541813068900456012262173614716378648849079776150946352466
e = 65537
p = 12591011258095671596958186047778684066366433713000083733603008978332296147605042520140224748454073644398378458146875090686440895644260506565719708746960331
q = 1779816733304736381084864812803761214302272494619817595962262887353495881068607828373749191179960417738609613170856737290048073479147894242862637932199748403
n = 22409692526386997228129877156813506752754387447752717527887987964559571432427892983480051412477389130668335262274931995291504411262883294295070539542625671556700675266826067588284189832712291138415510613208544808040871773692292843299067831286462494693987261585149330989738677007709580904907799587705949221601393
assert n == p*q
Cx = 10800064805285540717966506671755608695842888167470823375167618999987859282439818341340065691157186820773262778917703163576074192246707402694994764789796637450974439232033955461105503709247073521710698748730331929281150539060841390912041191898310821665024428887410019391364779755961320507576829130434805472435025
Cy = 2768587745458504508888671295007858261576650648888677215556202595582810243646501012099700700934297424175692110043143649129142339125437893189997882008360626232164112542648695106763870768328088062485508904856696799117514392142656010321241751972060171400632856162388575536779942744760787860721273632723718380811912
C=Point(Cx,Cy)
p1=(C*pow(e, -1, p+1)).x
p2=(C*pow(e, -1, q+1)).x
print(long_to_bytes(crt([p1%p,p2%q],[p,q])))
# flag{pHUCk_150M0rPh15m_1n70_p2}
Safe Curvy Curve
from Crypto.Util.number import *
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}"
D = 104195424559311137181271279442498654957365659039072230133307906910289876977215387204406606621273182995744469913980318794193540266885069529501579897759819085330481440863835062469771268905581027223137570462332151650553239341513789960350350245008144164176339007365876329719830893966710072622193879546377346644622
e = 65537
p = 166436420665281864493073460114157573042813073283547013806431669110780062035994416462859933677493469065525975357588079502758102291322213980236828429317373218004289118147507924337746527580216367842608357123948729908205501282083946942799175191877955092020698045112287067966169097483309308359153643953503334801203
q = 1954654839860678584456859051918235489548694929707217363339791396648354603632124085911991055478273417694240133422601529912376795611583072338269153142074826062829098920958253840849922510284025396208887863231665867835431714790114419935753780858219095409256769653096347662626969454843454197182893508787027
n = 325325755182481058670589439237195225483797901549838835146388756505962515992731682902174843378473793118013824587686743801443229435097379024643408429957717590072275498734396840489261986361764935791083084431387935565119970246214821662977047205360090509590387268197591520307878877103247121412898793371812283196864079961633428662039795223806526580626911586062085681619829271800589543048515261459541945856915535056363750996243146294104205192635607675773145823355324367791593757860302117944097894321078809559514655550115178790472355420484756646090492860950760854985816746318432545157312928351659730275368368710393481
assert n == p*q
Cx = 162961013908573567883708515220539578804107270477973090499542519193835498763624042601337274226440312066476160075983577251445943502548471650694617020354363039427231006183897304593798946447482514180041848851245384617847515040075915213698357885114317390276898478740949700799011676589252761736123613456698426984426140183972297018822418150981970598934664464599487393545946613698687046341448558294255407327000026161574779286948527797313848936686929888861150592859573221003557737086661845641459024783317432643308034709718127845066442672512067552552244030535478274512743971354192981490674475749853430371212307520421190
Cy = 239668740066200913943562381887193634676899220686058888912170632953311361194017666904277854011894382855202483252661143091091993190645295938873381009873178536800816517615786834926664362950059833369410239281041504946121643304746955139178731148307192034732522723412439705530514113775245607466575056817920259552225402143084439183697819510515790086246564683416312338905722676300264277098153045593619223527605305078928548583405756368607546463429755374790443440435124030514385157787083987202901009878849122637030860266764644062073632184729561756322435322264642199576207018861730005366413597578298926774145872631956206
C=Point(Cx,Cy)
p1=(C*pow(e, -1, p+1)).x
p2=(C*pow(e, -1, q+1)).x
print(long_to_bytes(crt([p1%p,p2%q],[p,q])))
# flag{p+1_factor_AND_150M0rPh15m_1n70_p2}
ColL3g10n
You can append bytes to the end of a md5 collision and it is still a collision!
We can use this to brute some with the matching sha256 prefixes too.
from Crypto.Util.number import long_to_bytes
from hashlib import sha256
from pwn import remote
io = remote("34.70.212.151", 8000)
def brute(a, b):
i = 1
while True:
m1 = bytes.fromhex(a) + long_to_bytes(i)
m2 = bytes.fromhex(b) + long_to_bytes(i)
if sha256(m1).hexdigest()[:5]==sha256(m2).hexdigest()[:5]:
return m1.hex(), m2.hex()
i += 1
def query(m1, m2, msk):
io.read()
io.sendline(m1.encode())
io.read()
io.sendline(m2.encode())
io.read()
io.sendline(str(int(msk, 2)).encode())
return int(io.readline().decode().split()[-1])
msk1 = "00000000000000000000000000000000000000000000000000000111011111110111111101111111"
msk2 = "00000000000000000000000000111111011111110111111101111000000000000000000000000000"
msk3 = "01111111011111110111111101000000000000000000000000000000000000000000000000000000"
known_md5_collisions = [
("0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef", "0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef"),
("4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2", "4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2"),
("a5e9e01ddad7d0b9411e2b5d70aeb9b84634835ac1d1ed916206803dee282b56c1e9b30cd024e0b6ef3fc8b208ecd528f44151d37d203d98856961a67788504ff667212bc4c5395b3cfff3491a3d116e25f3c6a75d30f9eb062dfb864cdbecce15a7fbee2f8d5008fa68019a8a44ca7edd30181573c3d3b0db609180272a2f6d", "a5e9e01ddad7d0b9411e2b5d70aeb9b8463483dac1d1ed916206803dee282b56c1e9b30cd024e0b6ef3fc8b2086cd628f44151d37d203d98856961267788504ff667212bc4c5395b3cfff3491a3d116e25f3c6275d30f9eb062dfb864cdbecce15a7fbee2f8d5008fa68019a8ac4c97edd30181573c3d3b0db609100272a2f6d")
]
rs = []
for (a, b), msk in zip(known_md5_collisions, [msk1, msk2, msk3]):
m1, m2 = brute(a, b)
rs.append(query(m1, m2, msk))
r1, r2, r3 = rs
secret = long_to_bytes(r1|r2|r3)
io.read()
io.sendline(secret)
print(io.read().decode())
# flag{S0m3_b1ts_y0u_kn0w_S0m3_b1ts_y0u_d0nt}
Secure_Matrix_Transmissions
Through eigenvalues of u and v we get permutations of the diagonals of a and b that can be bruteforced.
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
from base64 import b64decode
from itertools import permutations
from tqdm import tqdm
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)
p = 33184772290615481426295675425316668758122179640330548849957081783509
ct2 = b"8t5wC5gsdXOG7vDvw+uStOT1P2ZhB2FGsr/lvNaBMX+FAZ9aVY4UMOk8neL3KcELjQ3F62aX/sxN4KexO/krK2mm/v10qYrKbLPXljdwvck="
u = Matrix(GF(p),[
[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 = Matrix(GF(p), [
[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]
])
def solve():
for i in tqdm(permutations(u.eigenvalues())):
for j in permutations(v.eigenvalues()):
a = diagonal_matrix(GF(p), vector(i))
b = diagonal_matrix(GF(p), vector(j))
key = a + b
try:
flag = decrypt(ct2, key).decode()
return flag
except:
continue
flag = solve()
print()
print(flag)
# flag{In53cUr3_K3Y_3xch4ng3_0n_n0n-4b3L14n_gR0up5!!}
Secure_Matrix_Transmissions_v2
Upsolved using Genni’s code:
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib
from base64 import b64decode
import subprocess
from sympy.ntheory.modular import crt
from math import gcd
from collections import defaultdict
cado_path = "/home/connor/Documents/cado-nfs/cado-nfs.py"
def n_order(a, n):
if gcd(a, n) != 1:
raise ValueError("The two numbers should be relatively prime")
factors = defaultdict(int)
for px, kx in dict(factor(n)).items():
if kx > 1:
factors[px] += kx - 1
fpx = dict(factor(px - 1))
for py, ky in fpx.items():
factors[py] += ky
group_order = 1
for px, kx in factors.items():
group_order *= px**kx
order = 1
ff = {}
if a > n:
a = a % n
for p, e in factors.items():
exponent = group_order
for f in range(e + 1):
if pow(a, exponent, n) != 1:
order *= p ** (e - f + 1)
ff[p] = e - f + 1
break
exponent = exponent // p
return order, ff
def cado_dlog_unknown_base(p, ell, target):
out = subprocess.run(["python", f"{cado_path}", "-dlp",
f"{ell=}", f"{target=}", f"{p}"],
capture_output=True)
for line in out.stderr.decode().splitlines():
logbase_ = line.split("logbase = ")
logtarget_ = line.split("log(target) = ")
if len(logbase_) > 1:
logbase = int(logbase_[-1])
if len(logtarget_) > 1:
logtarget = int(logtarget_[-1].split()[0])
assert 1 == pow(pow(logbase, logtarget, p) * pow(target, -1, p), (p-1)//ell, p)
return logbase, logtarget
def cado_dlog(p, ell, a, base):
lb1, log_a = cado_dlog_unknown_base(p, ell, a)
lb2, log_b = cado_dlog_unknown_base(p, ell, base)
assert lb1 == lb2
dlog = (log_a * pow(log_b, -1, ell)) % ell
return dlog
def pohlig_hellman(n, a, b, order=None):
if order is None:
order, f = n_order(b, n)
l = [0] * len(f)
for i, (pi, ri) in enumerate(f.items()):
print(f'factor {pi}:')
for j in range(ri):
gj = pow(b, l[i], n)
aj = pow(a * pow(gj, -1, n), order // pi**(j + 1), n)
bj = pow(b, order // pi, n)
if pi < 2**58:
if is_prime(n):
cj = GF(n, proof=False)(aj).log(bj)
else:
cj = Zmod(n)(aj).log(bj)
else:
cj = cado_dlog(n, pi, aj, bj)
assert 1 == pow(pow(bj, cj, n) * pow(aj, -1, n), order//pi, n)
l[i] += cj * pi**j
d, _ = crt([pi**ri for pi, ri in f.items()], l)
return d
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 flag
p = 33184772290615481426295675425316668758122179640330548849957081783509
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]]
ct2 = '/PLzQibJlnw0CXQkeYEMwHJG3gjoOfEqF/cjLcSnIKB2oIwYqZ1R9Ro2XtE4R+g5nGEUqygGsxal7nYcqbjlMA=='
A = Matrix(GF(p), a)
B = Matrix(GF(p), b)
W = Matrix(GF(p), w)
u = Matrix(GF(p), u)
v = Matrix(GF(p), v)
psiA = A.charpoly()
psiB = B.charpoly()
Fpk = (psiA * psiB).splitting_field('z')
Ad, Sa = A.change_ring(Fpk).jordan_form(transformation = True)
assert Sa * Ad * Sa**-1 == A
Bd, Sb = B.change_ring(Fpk).jordan_form(transformation = True)
assert Sb * Bd * Sb**-1 == B
rhs = Sa**-1 * u * Sb
mid = Sa**-1 * W * Sb
order = p**10 - 1
base = Ad[1][1] / Ad[0][0]
targ = (rhs[1][0] / rhs[0][0]) * (mid[0][0] / mid[1][0])
bp = GF(p)(base ** (order//(p-1)))
tp = GF(p)(targ ** (order//(p-1)))
o1, _ = n_order(int(bp), p)
#n = pohlig_hellman(p, tp, bp)
n = 11666624338993671036969822837579727988282118013512505604714075291395
assert(bp**n == tp)
base = Bd[1][1] / Bd[0][0]
targ = (rhs[0][1] / rhs[0][0]) * (mid[0][0] / mid[0][1])
bp = GF(p)(base ** (order//(p-1)))
tp = GF(p)(targ ** (order//(p-1)))
o2, _ = n_order(int(bp), p)
#m = pohlig_hellman(p, tp, bp)
m = 919187230609799141228165294514978452312099248381283237794353795886
assert(bp**m == tp)
for k1 in range(5):
for k2 in range(5):
Ka = A ** (n + k1*o1) * v * B ** (m + k2*o2)
flag = decrypt(ct2, Ka)
if b"flag{" in flag:
print(unpad(flag, 16).decode())
# flag{In53cUr3_n0n-4b3L14n_d1Ff13_H31Lm4N!}