从一道题了解hnp问题和DSA加密

Crypto学习记录 DSA
Created At :
Count:1k Views 👀 :
  1. DSA算法
    1. 相关参数
    2. 签名过程
    3. 验证签名过程
  2. HNP（隐藏数字问题）
  3. DDSA

DSA算法

相关参数

  • $p：一个素模数，其值满足：2^{L-1} < p < 2^L，$

    $其中L是64的倍数，且满足512 <= L <= 1024$

  • $q：(p-1)的素因子，其值满足2^159 < q < 2^160，即q长度为160位。$

  • $g：g = h^{(p-1)/q}\space mod \space p。h为满足1 < h < p-1 的任意整数，$

    $从而有(h^{p-1}/q) \space mod \space p > 1$

  • $x：私钥。x为一个随机或伪随机生成的整数，$$其值满足 0 < x < q。$

  • $y：公钥。y = g^x \space mod \space p$

签名过程

  1. $产生一个随机数k，其值满足 0 < k < q$

  2. $计算r = (g^k \space mod \space p) \space mod \space q，其值满足 r > 0$

  3. $计算 s = (k^{-1}(SHA(M) + x \cdot r)) mod q，$

    $其值满足 s > 0$

$SHA(M)$表示明文的哈希值

一般给出$SHA(M)$和$(r,s)$

验证签名过程

  1. $计算 w = s^{-1} \space mod \space q$

  2. $计算 u1 = (SHA(M) \cdot w) \space mod \space q$

  3. $计算 u2 = (r \cdot w) \space mod \space q$

  4. $计算 v = (((g^{u1}) \cdot (y^{u2})) \space mod \space p ) \space mod \space q$

    $= ((g^{u1} \space mod \space p) \cdot (y^{u2} \space mod \space p) \space mod \space p) \space mod \space q$

    $= (g^{u1} \space mod \space p) \cdot y^{u2} \space mod \space p) \space mod \space p) \space mod \space q$

  5. 若$v$等于$r$，则通过验证，否则验证失败

参考：奇妙的安全旅行之DSA算法 - 知乎 (zhihu.com)

HNP（隐藏数字问题）

格密码中的HNP问题是指在格上找到一个短向量的问题。具体来说，给定一个格和一个正整数k，问题是找到一个长度小于等于k的非零向量，使得它在格中的长度最小。

格！

例题，来自2023闽盾杯线上初赛

DDSA

from random import randbytes
from hashlib import sha256
from secret import FLAG

prime_q = 127421879856060385096053898551127157118456253994158974724886976404028426764068562017096096817549513218041429679987628739034764964376732733276949462214328863705096240012832165273860133745796844957157858326462845401062317289670577559619496217615868033525902303096223754465050250835491302759273614202275099668351
prime_p = 2 * prime_q + 1
generator = 2

def generate_keys(prime_p:int, prime_q: int, generator: int):
    private_key = int(randbytes(48).hex(), 16)
    public_key = pow(generator, private_key, prime_p)
    return private_key, public_key

def signature(m: str, private_key: int):
    ephemeral_key = pow(int.from_bytes(m.encode(), "big"), -1, prime_q)
    value_r = pow(generator, ephemeral_key, prime_p) % prime_q
    hash_value = sha256(m.encode()).hexdigest()
    value_s = pow(ephemeral_key, -1, prime_q) * (int(hash_value, 16) + private_key * value_r) % prime_q
    return hash_value, value_r, value_s

def verification(message_hash: str, value_r: int, value_s: int, public_key: int):
    message_hash = int(message_hash, 16)
    inverse_s = pow(value_s, -1, prime_q)
    u1 = message_hash * inverse_s % prime_q
    u2 = value_r * inverse_s % prime_q
    value_v = (pow(generator, u1, prime_p) * pow(public_key, u2, prime_p) % prime_p) % prime_q
    return value_v == value_r

private_key, public_key = generate_keys(prime_p, prime_q, generator)
print(f"prime_p = {prime_p}")
print(f"prime_q = {prime_q}")
print(f"generator = {generator}")
print(f"public_key = {public_key}")
hash_value, value_r, value_s = signature(FLAG, private_key)
assert verification(hash_value, value_r, value_s, public_key)
print("FLAG= *******************************")
print(f"Here is your gift = {hash_value}")
print(f"value_r = {value_r}")
print(f"value_s = {value_s}")

标准的签名、验证签名的过程。

value_s = pow(ephemeral_key, -1, prime_q) * (int(hash_value, 16) + private_key * value_r) % prime_q

根据这一行，可得：

$s = k^{-1} \cdot (H(m)+x \cdot r) \space mod \space q$

因为$k = m^{-1} mod q$，所以$m = k^{-1} mod q$

上式改为：$s = m \cdot (H(m)+x \cdot r) \space mod \space q $

$x$为私钥，384位，$m$位明文，其它值均已知。

$H(m)^{-1} \cdot s = m +H(m)^{-1} \cdot x \cdot r \cdot m$

$H(m)^{-1} \cdot s -H(m)^{-1} \cdot x \cdot r \cdot m= m $

设$A = -H(m)^{-1} \cdot r $，$B = H(m)^{-1} \cdot s$

则$A \cdot x \cdot m + B = m \space mod \space q$

$x \cdot m < 512 \cdot 384(bits)$

$m<512(bits)$

对于$A \cdot x + B = C \space mod \space P$，若$x,C$位数不高，则可以求解。

构造格：

$\begin{pmatrix} q \ A & 2^{384+512}/2^{1024} \ B & &2^{512} \ \end{pmatrix}$

prime_q = 127421879856060385096053898551127157118456253994158974724886976404028426764068562017096096817549513218041429679987628739034764964376732733276949462214328863705096240012832165273860133745796844957157858326462845401062317289670577559619496217615868033525902303096223754465050250835491302759273614202275099668351
prime_p = 254843759712120770192107797102254314236912507988317949449773952808056853528137124034192193635099026436082859359975257478069529928753465466553898924428657727410192480025664330547720267491593689914315716652925690802124634579341155119238992435231736067051804606192447508930100501670982605518547228404550199336703
generator = 2

public_key = 221626515367647592774698098692118467726125002270923707776392092273852438126066246777603296829956250828415083664277762490845388121331825299028815885951560598279335233966636420997912034044513052659893707713433291450468987160769743831462128884319447474507303933872809094492673084193065131671470197353355700451803

gift = '2050bdda5527b5cf18f68200005a6bb62c4010013dab512f29d02e63df36571d'
value_r = 101864728107007256322146696835906604212197814524260866502407778313737287168856516069457310838661336537033173560412371160271358337973274492992529689773726394044125700941448246327965845614474447922873205529993062488526829237059305765805424195030256691004249492112249119165315964827635459697058222158680454166404
value_s = 14858213494892938274208295473099404970438428351803436618332274882154533757488885765771071391019660590987616021728381183464245690212466713501667728717924009493254516436772833023108348758817497242270007666442742087640045755313774846907435799204366653279367283728617752364710175015514694944532453955835006309850

A=ZZ(inverse_mod(int(gift, 16),prime_q)*value_r %prime_q)
B=ZZ(inverse_mod(int(gift, 16),prime_q)*value_s %prime_q)
RR=RationalField(1024)

M=Matrix(RR,3,3)
M[0,0]=prime_q
M[1,0]=-A
M[2,0]=B
M[1,1]=2^(384+512)/2^1024
M[2,2]=2^(512)
M.LLL()
'''
([287795483314674611984037243346852941780267693001967961176652694526257426569322525894740775171399472205152926475417993520383159162205803,660921158647686089810130735838387280055284741588297773638046453143607098752731801728172852883577729154595192695144091746468504654450331185251511173429985440569453378293161/1329227995784915872903807060280344576,],
[696184481681640001736822045923699700046331124959600139917503600623984103592157845998309070542164896421582743462023713769075764699063300,-33462575066006428445626846655763717451289413059285528293310029607219341890956799824162883901296968456544840614226505048488504153905139626050008376933751980598671814333152317/340282366920938463463374607431768211456,0],
[136143999223147653570475125291009323389,921247683803161234394155181720314122943264058437766005167195569112838136345218060634131944078209014480342992611790552083722269275378440683485195872427/5316911983139663491615228241121378304,13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096])
'''

flag = 136143999223147653570475125291009323389
print(long_to_bytes(flag))

对格的理解还不够，需要多做些题了，造格什么的还不会，暂且先记住方法吧。

参考：

2023闽盾杯线上初赛Crypto wp_无趣的浅的博客-CSDN博客

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com

©2022-2023 Luino

Built with Hexo and 3-hexo theme

github