{"id":94,"date":"2024-11-30T19:51:00","date_gmt":"2024-11-30T11:51:00","guid":{"rendered":"http:\/\/www.triode.cc\/?p=94"},"modified":"2025-09-28T09:39:04","modified_gmt":"2025-09-28T01:39:04","slug":"dirichlet-approximation-solution-hnp-2h","status":"publish","type":"post","link":"https:\/\/www.triode.cc\/index.php\/2024\/11\/30\/dirichlet-approximation-solution-hnp-2h\/","title":{"rendered":"\u901a\u8fc7\u72c4\u5229\u514b\u96f7\u8fd1\u4f3c\u89e3\u51b3HNP-2H"},"content":{"rendered":"\n

\u6700\u8fd1\u5728\u590d\u73b0Crypto CTF 2024\u7684\u65f6\u5019\u78b0\u5230\u4e00\u9053\u9898\u8003\u5bdf\u4e86HNP-2H\uff08Hidden Number Problem with 2 Holes\uff0c\u53cc\u6d1e\u9690\u85cf\u6570\u95ee\u9898\uff09\uff0c\u5728\u505a\u9898\u7684\u65f6\u5019\uff0c\u627e\u5230\u4e86\u4e00\u7bc7\u8bba\u6587\uff1aExtended Hidden Number Problem and Its Cryptanalytic Applications<\/a>\uff0c\u5e76\u901a\u8fc7\u8fd9\u7bc7\u8bba\u6587\u4e86\u89e3\u5230\u53ef\u4ee5\u901a\u8fc7\u72c4\u5229\u514b\u96f7\u8fd1\u4f3c\u5b9a\u7406\u6765\u5c06HNP-2H\u7ea6\u5316\u4e3a\u6211\u4eec\u719f\u6089\u7684HNP\u6765\u89e3\u51b3\u3002<\/p>\n\n\n\n

HNP-2H\u7684\u5b9a\u4e49<\/h2>\n\n\n\n

\u8fd9\u91cc\u76f4\u63a5\u5f15\u7528\u8bba\u6587\u4e2d\u7684\u5b9a\u4e49\uff1a<\/p>\n\n\n\n

\u8bbe\\(N\\)\u662f\u4e00\u4e2a\u8d28\u6570\uff0c\u5e76\u8bbe\\(x\\in \\mathbb{Z}_n\\)\u662f\u4e00\u4e2a\u90e8\u5206\u672a\u77e5\u7684\u6574\u6570\u6ee1\u8db3\u4ee5\u4e0b\\(d\\)\u6761\u540c\u4f59\u5f0f\uff1a<\/p>\n\n\n\n

$$
\\alpha_ix+\\rho_{i,1}k_{i,1}+\\rho_{i,2}k_{i,2}\\equiv \\beta_i\\pmod{N},\\ 1\\le i\\le d
$$<\/p>\n\n\n\n

\u5176\u4e2d\\(\\alpha_i\\)\u6ee1\u8db3\\(\\alpha_i\\mod{N}\\neq0\\)\uff0c\\(\\alpha_i,\\rho_{i,1},\\rho_{i,2}\\)\u4ee5\u53ca\\(\\beta_i\uff081\\le i\\le d\uff09\\)\u4e3a\u5df2\u77e5\u91cf\uff0c\u672a\u77e5\u91cf\\(k_{i,1}\\)\u4e0e\\(k_{i,2}\\)\u6ee1\u8db3\\(0\\le k_{i,1}\\le2^{\\mu_1}\\)\u53ca\\(0\\le k_{i,2}\\le2^{\\mu_2}\\)\uff08\\(1\\le i\\le d\\)\uff09\uff0c\u5176\u4e2d\\(\\mu_1,\\mu_2\\)\u4e3a\u5df2\u77e5\u6709\u7406\u5e38\u91cf\uff0c\u5219\u53cc\u6d1e\u9690\u85cf\u6570\u95ee\u9898\uff08Hidden Number Problem with 2 Holes\uff09\u5c31\u662f\u901a\u8fc7\u4ee5\u4e0a\u6761\u4ef6\u6c42\u51fa\\(x\\).<\/p>\n\n\n\n

\u4f7f\u7528\u72c4\u5229\u514b\u96f7\u8fd1\u4f3c\u89e3\u51b3HNP-2H<\/h2>\n\n\n\n

\u5728\u4f7f\u7528\u72c4\u5229\u514b\u96f7\u8fd1\u4f3c\u89e3\u51b3HNP-2H\u4e4b\u524d\uff0c\u6211\u4eec\u9700\u8981\u5148\u4e86\u89e3\u4f55\u8c13\u72c4\u5229\u514b\u96f7\u8fd1\u4f3c\uff0c\u5176\u9610\u8ff0\u5982\u4e0b<\/p>\n\n\n\n

\u72c4\u5229\u514b\u96f7\u8fd1\u4f3c\uff08Dirichlet’s approximation\uff09\u5b9a\u7406\u4ee5\u53ca\u5176\u63a8\u8bba<\/h3>\n\n\n\n

\u72c4\u5229\u514b\u96f7\u8fd1\u4f3c\u5b9a\u7406\uff1a<\/strong>\u8bbe\\(\\alpha\\in\\mathbb{R}\\)\u4ee5\u53ca\\(0<\\varepsilon\\le1\\)\u4e3a\u4e24\u5df2\u77e5\u91cf\uff0c\u90a3\u4e48\u5b58\u5728\\(p,q\\in\\mathbb{Z}\\)\u4f7f\u5f97\\(1\\le q\\le\\frac{1}{\\varepsilon}\\)\u4ee5\u53ca\\(|\\alpha-\\frac{p}{q}|<\\frac{\\varepsilon}{q}\\)\u6210\u7acb.<\/p>\n\n\n\n

\u901a\u8fc7\u8fd9\u4e2a\u5b9a\u7406\uff0c\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\u5982\u4e0b\u63a8\u8bba\uff1a<\/p>\n\n\n\n

\u5047\u5b9a\u6211\u4eec\u5df2\u77e5\\(A,N\\in\\mathbb{Z}\\)\u4e0e\\(B\\in\\mathbb{R}\\)\u6ee1\u8db3\\(B\\ge1\\)\u4e14\\(N>0\\)\u90a3\u4e48\u5b58\u5728\\(\\lambda\\in\\mathbb{Z}\\)\u6ee1\u8db3\\(1\\le\\lambda\\le B\\)\u4e14\\(|\\lambda A|_N<\\frac{N}{B}\\).\uff08\\(|a|_N\\)\u8868\u793a\\(min_{k\\in\\mathbb{Z}}|a-kN|\\)\uff09<\/p>\n\n\n\n

\u901a\u8fc7\u72c4\u5229\u514b\u96f7\u8fd1\u4f3c\u5b9a\u7406\u4ee5\u53ca\u5176\u63a8\u8bba\uff0c\u6211\u4eec\u53ef\u4ee5\u77e5\u9053\uff0c\u5728\u5df2\u77e5\\(B\\)\u7684\u60c5\u51b5\u4e0b\uff0c\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u8fde\u5206\u6570\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\u901a\u8fc7\\(|\\lambda A|_N<\\frac{N}{B}\\)\u6c42\u89e3\u51fa\\(\\lambda\\)<\/p>\n\n\n\n

\u501f\u52a9\u72c4\u5229\u514b\u96f7\u8fd1\u4f3c\u89e3\u51b3HNP-2H<\/h3>\n\n\n\n
\n

\u672c\u90e8\u5206\u6458\u81ea\u8bba\u6587\u7b2c\u4e09\u90e8\u5206\u7684 Theorem 3 \u7684\u8bc1\u660e<\/p>\n<\/blockquote>\n\n\n\n

\u4ee4\\(A_i=(\\rho_{i,1})^{-1}\\rho_{i,2}\\mod{N}\\)\uff0c\\(\\gamma_i=k_{i,1}+A_ik_{i,2}\\)\uff0c\\(\\alpha_i’=(\\rho_{i,1})^{-1}\\alpha_i\\mod{N}\\)\u4ee5\u53ca\\(\\beta_i’=(\\rho_{i,1})^{-1}\\beta_i\\mod{N}\\)\uff08\\(1\\le i\\le d\\)\uff09\uff0c\u5219\u540c\u4f59\u5f0f\\(\\alpha_ix+\\rho_{i,1}k_{i,1}+\\rho_{i,2}k_{i,2}\\equiv \\beta_i\\pmod{N}\\)\u53ef\u4ee5\u8f6c\u5316\u4e3a\uff1a<\/p>\n\n\n\n

$$
\\alpha_i’x+\\gamma_i\\equiv\\beta’_i\\pmod{N}
$$<\/p>\n\n\n\n

\u6211\u4eec\u9009\u5b9a\u4e00\u4e2a\u5927\u4e8e1\u7684\u5b9e\u6570\\(B\\)\uff0c\u7531\u72c4\u5229\u514b\u96f7\u8fd1\u4f3c\u7684\u63a8\u8bba\uff0c\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u8fde\u5206\u6570\u627e\u5230\u4e00\u4e2a\u975e\u96f6\u6574\u6570\\(\\lambda_{i,B}\\)\u6ee1\u8db3\\(|\\lambda_{i,B}A_i|<\\frac{N}{B}\\)\uff0c\u4e14\u6709\\(1\\le\\lambda_{i,B}\\le B\\)\uff08\\(1\\le i\\le d\\)\uff09\uff0c\u4f7f\u5f97\u4e0b\u9762\u7684\u5173\u7cfb\u6210\u7acb\uff1a<\/p>\n\n\n\n

$$
\\begin{aligned} |\\lambda_{i,B}\\gamma_i|_N &=|\\lambda_{i,B}k_{i,1}+\\lambda_{i,B}A_ik_{i,2}|_N\\\\ &\\le|\\lambda_{i,B}|_Nk_{i,1}+|\\lambda_{i,B}A_i|_Nk_{i,2}\\\\ &<B2^{\\mu_1}+\\frac{N}{B}2^{\\mu_2} \\end{aligned}
$$<\/p>\n\n\n\n

\u9009\u62e9\\(B_{min}=N^{\\frac{1}{2}}2^{\\frac{\\mu_2-\\mu_1}{2}}\\)\u53ef\u4ee5\u6700\u5927\u9650\u5ea6\u5730\u51cf\u5c11\\(B2^{\\mu_1}+\\frac{N}{B}2^{\\mu_2}\\)\u7684\u4e0a\u754c\uff08\u6b64\u65f6\\(B_{min}2^{\\mu_1}+\\frac{N}{B_{min}}2^{\\mu_2}=N^{\\frac{1}{2}}2^{\\frac{\\mu_1+\\mu_2+2}{2}}\\)\uff09.<\/p>\n\n\n\n

\u5728\u6b64\u4e4b\u540e\uff0c\u6211\u4eec\u8bbe\\(k_i’=\\left(\\lambda_{i,B_{min}}\\gamma_i+\\lfloor N^{\\frac{1}{2}}2^{\\frac{\\mu_1+\\mu_2+2}{2}}\\rfloor\\right)\\mod{N}\\)\uff0c\u53ef\u4ee5\u77e5\u9053\uff1a\\(k_i'<N^{\\frac{1}{2}}2^{\\frac{\\mu_1+\\mu_2+4}{2}}\\)\uff0c\u90a3\u4e48\u901a\u8fc7\u4e0b\u8ff0\u6b65\u9aa4\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u5c06HNP-2H\u8f6c\u5316\u4e3aHNP\uff0c\u4ece\u800c\u901a\u8fc7\u4e00\u822cHNP\u7684\u89e3\u51b3\u65b9\u6cd5\u6765\u89e3\u51b3HNP-2H\u4e86\uff1a<\/p>\n\n\n\n

$$
\\begin{aligned} \\alpha_i’x+\\gamma_i&\\equiv\\beta’_i\\pmod{N}\\\\ (\\lambda_{i,B_{min}}\\alpha_i’)x+\\lambda_{i,B_{min}}\\gamma_i&\\equiv\\lambda_{i,B_{min}}\\beta’_i\\pmod{N}\\\\ (\\lambda_{i,B_{min}}\\alpha_i’)x+k_i’&\\equiv\\lambda_{i,B_{min}}\\beta’_i+\\lfloor N^{\\frac{1}{2}}2^{\\frac{\\mu_1+\\mu_2+2}{2}}\\rfloor\\pmod{N}\\\\ \\alpha_i”x+k_i’&\\equiv\\beta_i”\\pmod{N},\\ (1\\le i\\le d) \\end{aligned}
$$<\/p>\n\n\n\n

\u4f8b\uff1a[Crypto CTF 2024] Honey<\/h2>\n\n\n\n

\u52a0\u5bc6\u4ee3\u7801\uff1a<\/p>\n\n\n\n

<\/circle><\/circle><\/circle><\/g><\/svg><\/span>