V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
liuidetmks
V2EX  ›  程序员

有没有哪种非对称算法,生成签名很难,校验很容易

  •  1
     
  •   liuidetmks · 2021-12-20 18:14:03 +08:00 · 3507 次点击
    这是一个创建于 829 天前的主题,其中的信息可能已经有所发展或是发生改变。
    用于接口验签
    客户端有数据 d 需要校验
    通过算法 H(d) = sign, 比如这个 H 算法每次计算耗费 1G Ram,10M 条指令。总之就是消耗资源,耗时 100 毫秒,又不影响用户体验。

    对应的服务端验签,比如有个密钥或者什么东西(key)能加速这个过程,使得验签算法 H2 验证很快,内存消耗也极小
    H2(d,key) = sign.


    举个简单例子,(理解意思就行,实际算法肯定是从 H 无法推算出 H2 的

    H(a) = a + (a + 1) + (a + 2) + (a + 3) + ... (a + 99) ; // 就是死算

    那么服务端 H2 直接验签 key = 4950;
    H2(a,key) = 100 a + 4950
    25 条回复    2021-12-21 15:00:31 +08:00
    ysjiang4869
        1
    ysjiang4869  
       2021-12-20 18:26:54 +08:00
    看看比特币的原理找点思路?
    ch2
        2
    ch2  
       2021-12-20 18:32:21 +08:00
    你目的是啥
    wy315700
        3
    wy315700  
       2021-12-20 18:39:17 +08:00
    这不就是最初的工作量证明么,Hashcash 用于防止垃圾邮件的。
    后来才用于区块链
    vToExer
        4
    vToExer  
       2021-12-20 18:46:40 +08:00   ❤️ 1
    工作量证明+1, 貌似可以任意指定一个 hash 函数 H(a, b), 先要求客户端找到一个 key, 使得 H(d, key)满足某种条件, 如包含 n 个前导零. 服务端拿到客户端发来的 key 后, 计算 H(d, key)简单校验即可.
    spiraldox
        5
    spiraldox  
       2021-12-20 19:21:55 +08:00   ❤️ 1
    可以去了解一下 delay function 或者 delay encryption ,利用这些密码学的基础算法应该可以实现你需要的功能
    xuanbg
        6
    xuanbg  
       2021-12-20 19:59:17 +08:00
    验签不是直接比较吗?根本就不花时间啊。
    liuidetmks
        7
    liuidetmks  
    OP
       2021-12-20 21:26:48 +08:00 via iPhone
    @ch2 防止接口被暴力破解被人刷数据。
    instalapple
        8
    instalapple  
       2021-12-20 23:08:58 +08:00
    离散对数问题?
    Thiece
        9
    Thiece  
       2021-12-20 23:49:47 +08:00
    ECC
    lingxi27
        10
    lingxi27  
       2021-12-21 00:20:20 +08:00   ❤️ 1
    如一楼的建议:

    1. 建立连接后,服务端生成随机数据 R 返回给客户端
    2. 协议规定,客户端必须找到数据 r 使得 sign=H(d+R+r)满足某种条件,比如低 n 位为 0
    3. 客户端再次提交(d, sign, r)
    4. 由于知道 r ,服务端可以很快验证签名
    agdhole
        11
    agdhole  
       2021-12-21 01:17:15 +08:00
    pow 老了,pos 向你招手
    geelaw
        12
    geelaw  
       2021-12-21 02:47:31 +08:00 via iPhone
    “耗费 1G RAM” “不影响用户体验”

    如果你想要计算需要大内存,你需要寻找 memory-hard function ;如果你要时间长,则需要 time-lock puzzle 。

    通常来说产生签名的人需要知道特殊的内容( key )。在楼主的场景下,验证签名的人因为有所谓的“快速验证”,所以知道(另一个)特殊内容( key )也算合理。但我没有明白搂住想要解决什么问题。
    holinhot
        13
    holinhot  
       2021-12-21 05:00:09 +08:00 via iPhone
    防 C C 攻击验证?
    liuidetmks
        14
    liuidetmks  
    OP
       2021-12-21 07:43:06 +08:00 via iPhone
    @geelaw 保护接口呀,举个例子,客户端发布后,肯定 H 方法会被人知道,甚至把代码提取出来做成动态库 ,通过这个库签发错误数据给服务器扰乱业务。

    如果能做到让他代价最大化,服务器收到错误数据最小化。前面 v 友说的 bitcoin 方式貌似不错。
    唯一问题是耗时是概率性的,总有可能有用户长时间算不出来
    geelaw
        15
    geelaw  
       2021-12-21 08:17:41 +08:00   ❤️ 2
    @liuidetmks #14 那么你不应该用“签名”,因为签名的最基本功能是让只有特定人才能产生有效签名,这里没有类似的场景。你可以用 #4 提到的 Hashcash ,通过恰当设置 scheme ,可以让长时间算不出来的概率可忽略,从而在一切现实场景下都不是问题;也可以用 #5 提到的 verifiable delay function 。

    实际操作里非密码学方法更常用,比如用业务逻辑限制访问频率。
    ElmerZhang
        16
    ElmerZhang  
       2021-12-21 08:30:51 +08:00
    感觉是用身份验证和频率限制可以解决的事情
    MoYi123
        17
    MoYi123  
       2021-12-21 09:27:23 +08:00
    分解质因数就行, 时间复杂度 O(n^0.5).
    生成一个合适的素数让客户端去分解.
    检验的时候,先用 miller-rabin 确定上传的都是质数,再乘起来检验结果.
    MoYi123
        18
    MoYi123  
       2021-12-21 09:28:00 +08:00
    @MoYi123 生成一个合适的数字(不是素数)让客户端去分解.
    exiledkingcc
        19
    exiledkingcc  
       2021-12-21 10:26:17 +08:00
    SM4
    exiledkingcc
        20
    exiledkingcc  
       2021-12-21 10:27:23 +08:00
    写错了,应该是 SM2 。
    exiledkingcc
        21
    exiledkingcc  
       2021-12-21 10:29:51 +08:00
    好吧,看了需求,SM2 也不符合。
    ruanimal
        22
    ruanimal  
       2021-12-21 10:35:09 +08:00   ❤️ 1
    难怪现在的网页和 app 越来越卡了,都啥呀
    liuidetmks
        23
    liuidetmks  
    OP
       2021-12-21 10:49:54 +08:00
    @ruanimal 环境太差, 恶意竞争太多了,没得办法啊。 我看过有的 app 直接用的 sleep 防止被恶意利用,但这容易被跳过。
    fromdark
        24
    fromdark  
       2021-12-21 14:19:13 +08:00
    @agdhole 但是 pos 面临着资本垄断的问题几乎是显著的
    strawberrydafu
        25
    strawberrydafu  
       2021-12-21 15:00:31 +08:00
    VDF
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5390 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 50ms · UTC 01:31 · PVG 09:31 · LAX 18:31 · JFK 21:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.