Rabin加密算法和n次同余方程 | 申博官网
登录
  • 欢迎进入申博官网!
  • 如果您觉得申博官网对你有帮助,那么赶紧使用Ctrl+D 收藏申博官网并分享出去吧
  • 这里是申博官方网!
  • 申博官网是菲律宾sunbet官网品牌平台!
  • 申博开户专业品牌平台!

Rabin加密算法和n次同余方程

申博_安全防护 申博 67次浏览 未收录 0个评论

媒介

Rabin算法是一种基于盘算模合数平方根难题性题目的非对称加密算法。他和RSA加密的情势相似,本文重要讨论Rabin算法的特殊状况和n次同余方程的解法。

Rabin算法

加密

挑选两个大素数p和q做为私钥

盘算n = p * q做为公钥

若明文为m,则密文为c ≡ m^2 (mod n)

解密

  1. 起首盘算出r和s,目标是知足:

Rabin加密算法和n次同余方程

这里的根号只是一种透露表现情势,透露表现Rabin加密算法和n次同余方程罢了,并非要真的去开方。一般挑选p和q都是模4余3的数,那末由欧拉鉴别定理:

  • 若是p为素数且***(a, p)=1,那末a是模p的平方盈余的充要前提是

Rabin加密算法和n次同余方程

把上式的a换成c,即
Rabin加密算法和n次同余方程
,那末把它带入
Rabin加密算法和n次同余方程
轻易获得
Rabin加密算法和n次同余方程
,则易得:

Rabin加密算法和n次同余方程

r和s的解其实有两个(一正一负),但这里只需知足前提就好了,以是恣意取一个正的就能够了

从这里能够看出来若是p和q不是模4余3的话,c的指数就不是一个整数,也就不能用这个要领盘算了

  1. 用扩大欧几里得算法盘算出a和b,使得:

ap + bq ≡ 1 (mod n)

  1. 解出四个明文:

Rabin加密算法和n次同余方程

  1. 算法正确性证明:

Rabin加密算法和n次同余方程

Uber Bug Bounty:将self-XSS转变为good-XSS

Uber Bug Bounty:将self-XSS转变为good-XSS 既然Uber bug赏金计划已公开发布,我可以发布一些我最喜欢的提交内容,这些内容在过去的一年里一直很想做。 在Uber的合作伙伴门户网站上,驱动程序可以登录并更新其详细信息,我发现了一个非常简单的经典XSS:将其中一个配置文件字段的值更改为 导致代码被执行,并弹出一个警告框。 注册后,这需要花费两分钟的时间才能找到,但现在又来了。 Self-XSS 能够在另一个站点的上下文中执行额外的,任意的JavaScript称为跨站点脚本(我假设99%的读者都知道)。通常,你希望针对其他用户执行此操作,以便抽取会话中的cookie,提交XHR请求等。 如果您无法针对其他用户执行此操作 – 例如,代码仅针对您的帐户执行,则称为Self-XSS。 在这种情况下,它似乎是我们发现的。你的个人资料的地址部分仅向您显示(例外情况可能是内部Uber工具也显示地址,但这是另一个问题),我们无法更新其他用户的地址以强制对其执行。 我总是想着是否发送有潜力的bug(这个站点中的XSS漏洞),所以让我们试着找出一种从bug中删除“self”部分的方法。 Uber OAuth登录流程 Uber使用的OAuth非常典型: 用户访问需要登录

关于其他的解也同理可证

p、q模4不余3

一般状况下挑选p和q的时刻,一般来说是挑选模4余3的素数的,然则若是两者不是模4余3的话,也是能够解的:

  1. 由m^2 ≡ c (mod n) 分解为两个同余式:m^2 ≡ c (mod p)和m^2 ≡ c(mod q)

  2. 关于上面的方程,若是模数是合数n的话盘算是难题的,但若是是素数的话就对照轻易,能够用二次同余方程的通用解法获得m ≡ C1 (mod p)和m ≡ C2(mod q)

  3. 个中C1和C2均有两个分歧的解,然后再用中国盈余定理联立上面两个方程就能解得m ≡ M (mod pq)了

个中二次同余方程解法的通用算法能够参考Cipolla’s algorithm,这里做一个简朴的诠释:

这个算法重要处置惩罚形如x^2 ≡ n (mod p), 个中p是奇素数的方程的x的解,解法以下:

设a知足w=a^2-n不是模p的二次盈余,即由欧拉定理
Rabin加密算法和n次同余方程
,那末
Rabin加密算法和n次同余方程
即为解,完成这个算法的话,重要的题目是根号w多是负数,能够界说实部和虚部应用疾速幂算法举行盘算,使得终究效果抵消掉根号,时候复杂度为O(log N)

测试的demo以下:

from Crypto.Util.number import getPrime
from random import randint
from libnum import *
from gmpy2 import *


def power(s1, s2, k1, k2, w, p):
    return ((s1*k1+s2*k2*w)%p, (s1*k2+s2*k1)%p)

def Cipolla_algorithm(p, n):
    a = randint(1, p)
    w = a ** 2 - n

    while pow(w, (p-1)/2, p) !=p-1 :
        a = randint(1, p)
        w = a ** 2 - n

    times = (p+1)/2

    k1 = 1
    k2 = 0

    first = True

    sum1 = 1
    sum2 = 0
    while times != 0:
        if first:
            k1, k2=power(k1, k2, a, 1, w, p)
            first = False

        else:
            k1, k2=power(k1, k2, k1, k2, w, p)

        if times & 1:
            sum1, sum2 = power(sum1, sum2, k1, k2, w, p)
        times >>= 1

    return sum1

def CRT(c, n):
    for i in range(len(n)):
        for j in range(i + 1, len(n)):
            assert ***(n[i], n[j]) == 1
    assert len(c) == len(n)

    N = reduce(lambda a, b: a*b, n)
    x = 0
    for i, j in zip(c, n):
        N_i = N/j
        N_i_1 = invert(N_i, j)
        x+=i*N_i*N_i_1
    return x % N

if __name__ == '__main__':
    p = getPrime(512)
    while p % 4 != 1:
        p = getPrime(512)

    q = getPrime(512)
    while q % 4 != 1:
        q = getPrime(512)
    n = p * q
    m = s2n('this is plaintext')
    c = pow(m, 2, n)
    print 'm is '+str(m)

    get_x1 = Cipolla_algorithm(p, c)
    get_x2 = Cipolla_algorithm(q, c)


    assert  pow(get_x1, 2, p) == c % p
    assert  pow(get_x2, 2, q) == c % q

    c11 = get_x1
    c12 = p-get_x1
    c21 = get_x2
    c22 = q-get_x2

    print 'possible m :' + str(CRT([c11, c21], [p, q]))
    print 'possible m :' + str(CRT([c11, c22], [p, q]))
    print 'possible m :' + str(CRT([c12, c21], [p, q]))
    print 'possible m :' + str(CRT([c12, c22], [p, q]))

n次同余方程

如许的话也就衍生了一个通用的解法,就是若是题目给的是m^e ≡ c (mod n),个中p、q已知然则e和phi(n)不互素的话,就能够应用上面的算法先解出m ≡ C1 (mod p)和m ≡ C2(mod q)再用CRT团结

但或许你会问m^3 ≡ c (mod p)或许m^n ≡ c (mod p),这类方程怎样求解,事实上这类方程的盘算是难题的,针对这个题目,python有sympy库能够举行处置惩罚,算法应该是应用的原根举行盘算,以是当p对照大的时刻盘算也是很难的,并且也不是一定有原根的:

from Crypto.Util.number import getPrime
from random import randint
from sympy.ntheory.residue_ntheory import nthroot_mod

p = getPrime(150)
x = randint(1, p)
n = pow(x, 4, p)

x1 = nthroot_mod(n,4,p,all_roots=False)
assert pow(x1, 4, p) == n
print x1

然则若是碰到如许的题目场景,且p、q不是迥殊大的话,也能够实验一下,说不定就能解呢 :D

总结

Rabin加密算法一般在CTF里和RSA结合起来考,若是上面的看的不是很邃晓的话,在今后碰到这类相似的状况(p、q模4不余3 或许 上面说到n次同余方程的场景),就能够直接用我的exp解了,不消再去暴破了 :D


申博|网络安全巴士站声明:该文看法仅代表作者自己,与本平台无关。版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明Rabin加密算法和n次同余方程
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址