The flag is encrypted by this code, can you decrypt it?
crosscheck.tar.xz
Summary: breaking RSA modulos with related primes.
In this challenge we have 3 RSA modulos and 3 parts of flag encrypted. Here’s how the keys are generated:
p = random.randint(1 << 510, 1 << 511) q = random.randint(1 << 510, 1 << 511) for i in range(0, 3): p = gmpy.next_prime(p) q = gmpy.next_prime(q) P.append(p) Q.append(q) for i in range(0, 3): N.append(P[i] * Q[2 - i]) |
All the primes are very close to each other. Each modulus is related to any other: one factor is slightly increased, another one is slightly decreased.
Note: if both factors were slightly increased (e.g. N[i] = P[i] * Q[i]), then it would be easy to break with Fermat method for factorization for N[0] * N[1]: it would yield us P[0]*Q[1] and P[1]*Q[0] and then GCD would reveal all the factors.
Let’s look closer at some pair of modulos, let’s say N[0] and N[1] (p and q redefined for simplicity):
- $N_0=p*(q+s_q)$
- $N_1=(p+s_p)*q$
We want to exploit the fact that $s_p$ and $s_q$ are small (we can bruteforce them). Consider linear combination of this modulos:
$$c = a N_0 + b N_1 = p q(a + b) + a p s_q + b q s_p$$
If we consider this modulo (a + b) then we will have:
$$c \equiv{} a p s_q + b q s_p \pmod{a + b}$$
Let M be some large prime,a=1 and b=M-1. Then
$$c \equiv{} p s_q – q s_p \pmod{M}$$
And if M is large enough, modulo reduction can be dropped and we will learn the exact value of
$$c \mod{M} = p s_q – q s_p$$
UPD: I just realized that modulo M is not needed at all. Simply
$$c = N_0 – N_1 = p s_q – q s_p$$
Having this linear combination of p and q we can easily bruteforce $s_p$ and $s_q$ and factor all the modulos!
$$\Rightarrow{} p = \frac{c + s_p q}{s_q}$$
$$\Rightarrow{} N_0 s_q = (c + s_p q)(q + s_q)$$
$$\Rightarrow{} q^2 s_p + q(c + s_p s_q) + s_q(c + N_0) = 0$$
(quadratic equation over integers with unknown q).
The code:
M = gmpy.next_prime(1 << 1000) C = (N[0] + (M - 1) * N[1]) % M if C > M / 2: # p s_q - q s_p can be negative C = -(M - C) p_sp = None for sp in xrange(1, 2000): for sq in xrange(1, 2000): # solve quadratic equation over ZZ a = sp b = C + sp * sq c = sq * (C - N[0]) D = b ** 2 - 4 * a * c if D < 0: continue sqrD = D.root(2)[0] if sqrD ** 2 != D: continue for add in (-sqrD, sqrD): q = (-b + add) / (2 * a) if N[1] % q == 0: p_sp = N[1] / q break if p_sp: break assert p_sp, "no solution?" P = [None] * 3 Q = [None] * 3 P[2] = gmpy.next_prime(p_sp) Q[0] = N[2] / P[2] Q[1] = gmpy.next_prime(Q[0]) Q[2] = gmpy.next_prime(Q[1]) P[0] = N[0] / Q[2] P[1] = gmpy.next_prime(P[0]) assert P[0] * Q[2] == N[0] assert P[1] * Q[1] == N[1] assert P[2] * Q[0] == N[2] cts = [ "DjXmcsw0QXBRBiUOx2Uu4kS/gFvIYyf6MSJLWlwy8i7WjVB8vOtUb90GTFSuHDX6iawvUg/XVjU7DVAi9EhMGSS2LyvgMH4nD4gjlVlC2PkxkNDILuUq//5DMoTUyootReoke1jXDnmHg1y0KglkIylL2dufsHc74cAKnciNU9U=", "DkYN4JwQU+EstIvIs662BISkzXxqqfb62DrJFV5efVuXtkLSQrzHgLczgC1blF8e29x46Jz2yjqb1eb2IJX59yuDBHiQ13ckId+E732Bpu00ee9UqYtSNNnQFIo8LIBWFxIUK3+XjNynDD9ArcF5OkLvk8o8AU1DcAdusQtsURo=", "CuMo9lJNex64Wh63DORfMPkcwX7inwNd3QEi/OKb2vbh69v4iF46/4tCz8ZF7FEKfNxmXuyPREdS7YPqNGi9hQT21CmeiXe/AbDCITrhYVMWJi4A6wjZjkdslHklnmJFnULRkSLVCYAgVQAbPGO3CmQ+3y9QSAhZM5qi8NQnoOo=" ] for i in range(0, 3): d = gmpy.invert(long(65537), (P[i] - 1) * (Q[2 - i] - 1)) priv = RSA.construct((long(N[i]), long(65537), long(d), long(P[i]), long(Q[2 - i]))) priv = PKCS1_v1_5.new(priv) ct = cts[i].decode("base64") print priv.decrypt(ct, None) |
$ time py cross_check.py hi all the flag is ASIS{a0c8f997d5cdd6 99d336b0f2f12af326} real 0m1.110s user 0m1.091s sys 0m0.016s |
5 comments
Skip to comment form
Ферма тоже работает.
https://b01lers.net/challenges/ASIS%202015/Cross%20Check/52/
что мы делали нет так ;(
Но крутости решения “by hellman” это не отменяет)
Author
Да, видимо нужно просто не останавливаться на первой выдаче от Ферма (которая даст уже известную факуторизацию на N1 * N2), а продолжать алгоритм.
кто-то просто метод Ферма криво закодил (и не проверил) и оно вообще ниче никогда не выводило ;)
der.Another approach is when your customer subscribes at an individual’s sight will send proof messages which usually their demand was attained though instead of simply saying, “we have received your request” add something extra within.This is a great time to consider them a specifder.Another approach is when your customer subscribes at an individual’s sight will send proof messages which usually their demand was attained though instead of simply saying, “we have received your request” add something extra within.This is a great time to consider them a specific thing extra from your sight or simply a discount down there so next purchase, be creative and will also be amazed at the responses you are going to receive.
The incredible importance of this approach could be to let your visitors know that you are following-up with them to cause them to become happy in relation to their purchase and therefore if they’ve got any problems or concerns they will contact one.Do not overwhelm him or her with sales pitches let that are a 2nd message.Get them to be feel that you really cherish their satisfaction with your product.
Most people prefer to search at a place and essentially examine goods they’re just interested within purchasing very first hand.In such a case, some good obsessed about Kohl’s website are sold for their store, so a possible client could potentially proceed to the store, evaluate an supplement and buy it’s confidential counterpart online at its website.Bare in view that Kohls aren’t able you can sell organic the equal low fees on solutions at his or her’s stores for the reason that what you have access to from their website.While merchants should price match to the websites, you cannot assume all do, so will not assume that you may walk right store and they’re going to honor most of the
Most people prefer to search at a place and essentially examine goods they’re just interested within purchasing very first hand.In such a case, some good obsessed about Kohl’s website are sold for their store, so a possible client could potentially proceed to the store, evaluate an supplement and buy it’s confidential counterpart online at its website.Bare in view that Kohls aren’t able you can sell organic the equal low fees on solutions at his or her’s stores for the reason that what you have access to from their website.While merchants should price match to the websites, you cannot assume all do, so will not assume that you may walk right store and they’re going to honor most of the website fees.In a number of companies, their virtual reality inventory and pricing shape is handled differently given that they aren’t incurring the equivalent expenses to be a offline outlet could be, so their income is extremely different.
If you want obtaining some sort of discount anytime shopping on Kohl’s website, keep planned discounts may be not stackable, meaning it’s hard to use more then one per obtain and aren’t combine these folks with other bargains, coupons, profits, etc.This is certainly pretty usual place amongst secure password manager stores.Kohl’s coupons might be a dollar based upon, meaning you may save some sort of specified dollars amount each order if you ever order whole is over a specific amount, or it will likely be a proportion off a good purchase in case you meet most of the requirement and even or conditions.
Remember the fact that Kohls is just not the sole website to make use of promotions via online codes and price reduction links.Many stores by having a web presence make use of offering their prospective customers hidden treasures similar to the ones earlier on they just may not in obvious site and may take a certain amount of searching on your favorite online search engine to discover your price cut.Whether or not you will discover any offers can be found at the amount of time you tend to be shopping is choice, the purchaser, to learn.