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

一个数学问题,关于 RSA 里的 e 的问题。

  •  
  •   saranz · 217 天前 · 2141 次点击
    这是一个创建于 217 天前的主题,其中的信息可能已经有所发展或是发生改变。
    关于 RSA 里,e 是怎么得出的问题。
    B 站看了半天没看明白……
    也没有一个视频说明的这个 e 怎么来的,搜了半天也没有结果。
    咱这脑子真的不明白……
    请各位数学大师傅给说说个明白呗。

    p= 11, q= 19
    φn= (11-1)(19-1)

    e 取 7 。<== 这个 7 是怎么计算出来的,是随便取的一小于 φn 的质数,还是是经过什么过程计算出来的?
    16 条回复    2024-05-25 18:06:55 +08:00
    adoal
        1
    adoal  
       217 天前
    理论上随便选都可以。但是随便选的作为幂有可能会导致计算量太大。
    PEM 建议用 3 ,X.509 建议用 65537 ,PKCS#1 建议用两者之一。
    tool2dx
        2
    tool2dx  
       217 天前 via Android
    数学上无所谓,代码里要用到中国剩余定理,那就只能选特定的 e
    rabbbit
        3
    rabbbit  
       217 天前
    随便选的
    https://en.wikipedia.org/wiki/65,537

    65537 is commonly used as a public exponent in the RSA cryptosystem. Because it is the Fermat number Fn = 22n + 1 with n = 4, the common shorthand is "F4" or "F4".[3] This value was used in RSA mainly for historical reasons; early raw RSA implementations (without proper padding) were vulnerable to very small exponents, while use of high exponents was computationally expensive with no advantage to security (assuming proper padding).[4]
    rabbbit
        4
    rabbbit  
       217 天前
    随便选,条件是 1 < e < λ(n) 并且 e 和 λ(n) 互质
    saranz
        5
    saranz  
    OP
       217 天前
    @rabbbit 就这个条件完全搞不明白…… 究竟是要计算出来还是随便找个小于 φn 的质数。


    @tool2dx 中国剩余定理?
    rabbbit
        6
    rabbbit  
       217 天前
    不懂,我以为就是随便选了个质数。
    看看这里,也许有帮助。

    https://en.wikipedia.org/wiki/RSA_(cryptosystem)

    e having a short bit-length and small Hamming weight results in more efficient encryption – the most commonly chosen value for e is 216 + 1 = 65537. The smallest (and fastest) possible value for e is 3, but such a small value for e has been shown to be less secure in some settings.
    rabbbit
        7
    rabbbit  
       217 天前
    谁能讲讲这个 small Hamming weight 的作用?
    saranz
        8
    saranz  
    OP
       217 天前
    @rabbbit 哎,不仅数学不会,English 还不懂,咱果然不适合研究这么深奥的学问。

    看了半天,我的理解是,一个小于 φn 且是相对小的数。
    但是不知道这是不是正确的理解。
    lDqe4OE6iOEUQNM7
        9
    lDqe4OE6iOEUQNM7  
       217 天前

    𝑝
    =
    11
    p=11 和
    𝑞
    =
    19
    q=19 ,所以:

    𝜙
    (
    𝑛
    )
    =
    (
    𝑝

    1
    )
    (
    𝑞

    1
    )
    =
    (
    11

    1
    )
    (
    19

    1
    )
    =
    10
    ×
    18
    =
    180
    ϕ(n)=(p−1)(q−1)=(11−1)(19−1)=10×18=180
    lDqe4OE6iOEUQNM7
        10
    lDqe4OE6iOEUQNM7  
       217 天前
    p = 11;
    q = 19;
    n = p * q;
    phiN = (p - 1) * (q - 1);
    e = 7;
    GCD[e, phiN]
    lDqe4OE6iOEUQNM7
        11
    lDqe4OE6iOEUQNM7  
       217 天前
    验证 7 和 180 互质性:
    gcd(7,180)=1
    saranz
        12
    saranz  
    OP
       217 天前
    @James2099 所以这个 7 究竟是怎么来的,是随便从小于 phiN 的质数里找一个呐,还是需要计算出来一个质数呐。
    marat1ren
        13
    marat1ren  
       217 天前 via iPhone
    一般都先从 65537 ,如果 65537 不满足验证条件就从小的质数开始,比如 3 。
    pxiphx891
        14
    pxiphx891  
       217 天前
    可以看一下这一节: https://datatracker.ietf.org/doc/html/rfc8017#section-3.1

    写的很清楚:「一个有效的 RSA 公钥中,RSA 模数 n 是 u 个不同奇素数 r_i 的乘积,i = 1, 2, ..., u ,此处 u >= 2 ,而 RSA 公钥指数 e 是一个介于 3 和 n - 1 之间的整数,满足 e 与λ(n)的最大公约数为 1 ,其中λ(n) = r_1 - 1, ..., r_u - 1 的最小公倍数。按照惯例,前两个素数 r_1 和 r_2 也可以分别表示为 p 和 q 。」
    jedrek
        15
    jedrek  
       217 天前 via Android
    234ygg
        16
    234ygg  
       211 天前   ❤️ 1
    e 随便取的,比 n 小 并且与φn 互素就行了。
    这种算法实际上没啥用,教科书式算法,你会发现 p 和 q 的位数稍微大一点就因数分解不出了。
    如果我没记错的话,p = random_prime(2^(k/2)),这里的 k 到 270 左右就很难解了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4131 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 05:30 · PVG 13:30 · LAX 21:30 · JFK 00:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.