[NSSRound#11 Basic]NTR

题面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import gmpy2
from flag import flag
from Crypto.Util.number import *

def init():
    p = getPrime(2048)
    while True:
        x = getRandomNBitInteger(1024)
        y = getPrime(768)
        z = gmpy2.invert(x, p) * y % p
        return (p, x, y, z)

def encrypt(cipher, p, z):
    message = bytes_to_long(cipher)
    r = getRandomNBitInteger(1024)
    c = (r * z + message) % p
    return c

p, x, y, z = init()
c = encrypt(flag, p, z)
with open("cipher.txt", "w") as f:
    f.write("binz = " + str(bin(z)) + "\n")
    f.write("binp = " + str(bin(p)) + "\n")
    f.write("binc = " + str(bin(c)) + "\n")

'''
binz = 0b10000100100000110000100001011001100110110111111110101001011100111001101101100100010010100110111010000001000001100011111011011000110000000111011100100010010001100110101001001110011000110000100101111001101010000101001101010001111001110000010100011001101010111000110111011111100101100100101100111000101011111101111011000101000100000010100100000110000001011100011100010001101001100101100100000101101101001100110100100101110000011001000000000010100010100011001100110101011000010000001111100101001001110111000110010001101111111110000111100001110011100001101010001101010011011110101100100110110011001111110111100100000011101000000100010011101110111100111100111100011001000111010110100101100110111101010010111110000100100001110101011000010101110010010100101110001001101010101001100000111010011110001000010100000100010000010000110011100111100110011100110111101011101001000110110011001011010101100110111111110001011110000100100011110111100011111011111011100110011011100010111010110010111101010001100010001010010111111101110011010101000010000011100000110001100110100001010011010111000000110001010110000110000000100111000101010000010100000110111111111001100100101001111001010010101101101100111010000001100101100100101010111010000011101000100011011111010101100000011100100101110001100100010010010100010000100100100111101101110110111101011001111011011101001110110100101111110001010110010000101111011110111011100111100110000110000010101001101001101000111010100110011000101010001110100110101101110011111010110010010111110111101100111100101110110011110100100000101000101100111000100011001111110001000010010001010101110001110000111100110001101111110110001001001100101110001010111111000111000100011001110001010101000100110001000101110110101000000001100010001000101110000000010001001001100110100100011100101101010010100001011111001011010011001000101101101001111001100101011101111110111101101100111110000100110110011110000111111011010010010011011100100101000000111110110010101110010011000111101101011111110001100101100011111110111111100111001011001010010101000011001110

binp = 0b10011001100000011101010111000011011000001101101000010101101110001111101010101100110000100111101101000100011101001011001100101000110010001000100001010011011100110011001110111001101010000111100000111110110101011101110000010111111101101111001011111111101100010011010001000011000100000010111111001000100000010001010001110101101011001100110001100000001100111010010011010101000011001101111011001110101111111011111101010100100000111101010101001101110000010101100011111001111100001100111010000111100110000001010001001101111111111100010010010001100110000011100110100100001000001001011010000000010100100011001000000000000010100111010011000111011010001010111010001000101100101011001001101101001101101001110101111011010110100101000000001111000001100101000000010101011011011100000001010001111000000100110011011001010011101000010101100101001000001100111001101000111101000000111001110010100001111100101001001101001101000011111001001000101001100101010001011010101111001001101110011101011001011110000001000100100110110001011010101000111001111001011001000001011111110000111000001100011110000011001110000010110101010000000101001111111011100010000000111001110100000010001101100110111010100000011101000100111011111011110001011001110000010001101010011110100110100111001000100010000110110110010111100101111010011110011110100000001001110111100111101000100011011100011101111100101100110110100011101110001111111110010001000001101111100100101011111110111110010100101010110111010111110010110111101011101111110110110101001111101101000010010100000101111000100010110100010011101000100111000011111100111010011010011101110110000100101100101010111111000110100010010101001000001111001100100110101000100110101001011110111101010101110001111101111001110000101000001010110011111000000010010100010000111011001000111000011000011110100000111101101011100000101000111011101110101100101001110001101000111100111011110000110010101010000100110100011010111110111100010111111101010110001000010010011110111101000110001100101111000111101010101101101100100010110011101111101000011101100000101001111001

binc = 0b1111010111110100110011100100001100111101111000010010000010010011101110101000101000100011111101011100110010010111111010000111001101010101010111100000000100111111001111110001111011110100001111001001010001000000011110000001001000011010100111100011110011011010011010011011111111100100110000110010011101110111001001011010101001101011100110101110001111111100100111011010011001001001100010110100000011100000000100110010101100000001010000101000100010000101101111010101000001000110011101100101010111110111000100001011110101010011010010110111010010100101001001010011000100110010010010110100101001111001111000011011000000110000111111001101001111010011110101001001111111110001001100011100101100011110110101000110010110110110101110110110111010110111100101101000111101101011000010011001111111010111000001100101001010010110111100100100100011110101010010010010010100100011001100011111010011101101101101000010101101011000100101101100001000000001101111111100100101111000101011001010010011000011001101101110101001011111010110000111111111011000101100000000011001010000000111110000001101101100101010010001101101010101000010010010110101110100100110011001001011101011111110011100000100001100010100000101011100001110101101011011110000101110011011100010100101010011101011001011011111100001100010000010110010001111010000110010000011100010010101110000101011110000111101001110001111111111101011000110001111011100100111000010110001111110100100011110000100010000011101110101111101000110100110111101110001011101110100001101101100011111000010101111100011100011011001011110010000000001010010101100111001111110110101000010110101110001011000101101110100110111100000110101101010010111001101000010001101110011101010111111011001110000001110000110001000101110110010001001001101010011110100000010100000100010110000001000011001011010000010111010100100101010100010011001100111011110111100101111100000100110110110101101110100011011101101100000101111000011110011000010000000100010000011110110010000010101001110000111110111110001001101000010011101010101101111101010100001101010111010000010000
'''

分析：

我们看一下能否用LLL格基规约算法，看Hermite定理是否满足：
$$
||v||\ \leq\ \sqrt{n}det(L)^{\frac{1}{n}}\
||v||\ =\ \sqrt{f^2+g^2}\
\sqrt{n}\ =\ \sqrt{2}\
det(L)^{\frac{1}{n}}\ =\ (1p-h0)^\frac{1}{2}
$$

通过粗略计算，||v||约等于2^1024^，因为有根号2右侧要比2^1024^大，所以可以使用LLL格基规约算法。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
z = ...
p = ...
c = ...

M = matrix([[1,z],[0,p]])
L = M.LLL()
ans = L[0]
if ans<0:
    ans = -ans
f,g = ans
a = c*f%p
m = a*pow(f,-1,g)%g
print(long_to_bytes(int(m)))

第二届黄河流域网络安全技能挑战赛-easyntru

题面:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from secret import flag
import libnum

bits = 2048
while True:
  q = random_prime(2^bits, lbound=2^(bits - 1))
  f = random_prime(2^(3*bits//4 - 1))
  g = random_prime(2^(bits//4 - 1))
  if gcd(f, q*g) == 1:
    h = f.inverse_mod(q) * g % q
    break
r = random_prime(2^(3*bits//4 - 1))
m = libnum.s2n(flag)
assert m < 2^(bits//4)
c = (r * h + m) % q

print('q = %d' % q)
print('h = %d' % h)
print('c = %d' % c)
'''
q = 24445829856673933058683889356407393860808522483552243481673407476395441107312130500945533047834993780864465577896968035259377721441466959027298166974554621753030728893320770628116412892838297326949997096948374940319126319050202262831370086992122741039059235809755486170276098658609363789670834482459758766315965501103856358827004129316458293962968758091319313119139703281758409686502729987426264868783862562150543872477975124482520151991822540312287812454562890993596447391870392038170902308036014733295394468384998808411243690466996284064331048659179342050962003962851315539367769981491650514319735943099663094899893
h = 4913183942329791657370364901346185016154546804260113829799181697126245901054001842015324265348151984020885129647620152505641164596983663274947698263948774663097557712000980632171097748594337673511102227336174939704483645747401790373320060474777199502879236509921155985395351647045776678540066383822814858118010995298071799515355111562392871675582742450331679030377003011729873888234401630551097244308473512890467393558048369156638425711104036276296581364374424105121033213701940135560177615395895359023414249846471332180098181632276243857635719541258706892559869642925945927703702696983949003370155033272664851406633
c = 23952867341969786229998420209594360249658731959635047659110331734424497403162506614140213749790708068086973241468969253395309243550869149482017583754015801740198734485871141965939993554966887039832701333623276590311516052334557237678750680087492306461195312290860900992532859827406262394480605001436094705579158919540851727801502678160085863180222123880690741582667929660533985778430252783414931317574267109741748071838599712027351385462245528001743693258053631099442571041984251010436099847588345982312217135023484895981833846397834589554744611429133085987275209019352039744743479972391909531680560125335638705509351

分析：

我们还是先分析，是否满足了Hermite定理：
$$
(f,-k)*\begin{bmatrix}
1 & h\
0 & p
\end{bmatrix}\ =\ (f,g)\
题目中提供的\ g=512bits,f=1536bits,q=2048bits\
与上一题不同的是:上一题是f = \theta(g),但本题是f=O(g)
$$

更紧的界：

一般考虑的都是x = Θ(y),如果x=o(y)或者y=o(x)我们首先假设：
$$
x\ =\ \theta(P^\alpha)\
y\ =\ \theta(P^\beta)\
$$
根据上面构造的v * M = w:
$$
(x,k)*\begin{bmatrix}
1 & A\
0 & P
\end{bmatrix}=\ (x,y)
$$
有：
$$
w\ \approx\ (P^\alpha,P^\beta)
$$
推算一下的话可知道，w的长度其实是由"最大"的元素决定的，就是说假设
$$
\alpha>\beta\
有：\ ||w|| \approx\ \sqrt{2}P^a
$$
也就是如果对w和M的第二列同乘一个c，使得a=Θ(cb)，