文章目錄
  1. 1. Smooth As Silk
    1. 1.0.1. Pollard p-1因子分解法
    2. 1.0.2. 实际的Pollard p-1
  • 2. Rail Fence Cipher
  • 3. URE
  • 4. High-speed RSA Keygen
  • 5. Impossible Game
  • 6. Hail Zeus
  • SharifCTF2016

    Smooth As Silk

    p > q
    n = p*q = 11461532818525251775869994369956628325437478510485272730419843320517940601808597552925629451795611990372651568770181872282590309894187815091191649914833274805419432525386234876477307472337026966745408507004000948112191973777090407558162018558945596691322909404307420094584606103206490426551745910268138393804043641876816598599064856358266650339178617149833032309379858059729179857419751093138295863034844253827963
    flag = md5(str(p))
    

    题解说用Pollard p-1因子分解法,然而这几种因子分解法我都忘记了。必须得复习Stinson的书了。看懂方法,看懂证明,会用方法,看到方法就能想出证明的大致思路,能轻松写出代码。我想就是这几个步骤。否则就会像之前一样,连欧拉公式的证明,欧几里德定理三种形式的证明都不会。
    至于为什么我用RSA-Tool 2的Pollard p-1解不出来,就不清楚了。
    趁此机会复习Pollard p-1。用不严谨的语言来解释。。

    Pollard p-1因子分解法

    $a \leftarrow 2$
    $for j \leftarrow 2 to B$
    $\qquad do a \leftarrow a^j mod n$
    $d \leftarrow gcd(a-1,n)$
    $if 1 < d < n$
    $\qquad then return(d)$
    $\qquad else return(“failure”)$

    这个算法的唯一参数就是界B
    p-1名字的由来就是Fermat定理。

    用了四个条件或者说工具
    一、Fermat定理得到$2^{p - 1} \equiv 1 (mod p)$
    二、(p-1)|B!(只要我们的B取得好,下面来讨论B的取值)
    三、$a \equiv 2^{B!}(mod n)$(由循环迭代得到的)
    四、p|n

    一和二结合一下,两者都有p-1,我们可以把2的幂次转换成B!(之所以要做这个循环迭代就是为了这个目的)
    三和四结合一下,可以把模从n变成p
    最后全部整合,Fermat定理右边的1,变到现在同余式右边,三中a变到同余式的左边。即$a \equiv 1 (mod p)$

    得到了p|(a-1),而且p|n,所以p|d,其中d=gcd(a-1, n)。只要d在1~n-1间就可以计算出一个d是n的非平凡因子。

    什么叫B取得好:n的每一个素数幂q|(p-1),都有$q \leq B$,素数幂是指素数的任意次幂(以最高次幂来理解就容易理解了)。因为B! = 1*2*3…*B

    总的来说,Pollard p-1就是通过找到p的一个倍数(a-1),结合p的倍数n,来使素数测试,转化为gcd测试,降低复杂度。

    不再深入分析复杂度了。

    实际的Pollard p-1

    之前的是教科书式因式分解,注意到两个问题:一、底数非得是2吗?二、a只和p-1的最高次幂有关,能不能降低a?$2^{B!}$有些大

    一、四个条件中只有费马定理用到了这个底数2,因此只要(a,p)=1即可。
    因此我们在分解过程中,底数也是需要更换的(换别的质数,否则有的因子就分解不出来,因为此时可能$2^{B1} \equiv 0(mod 4)$)

    二、我们不清楚p-1有哪些素数幂,但是我们可以尝试,只要满足了:B1至少包含所有p-1素数最高次幂,就保证了(p-1)|B1,并不需要B1取B!
    于是我们可以从小到大枚举所有素数,和它们的幂次(小于等于最高次幂),累积,并检验,直到B1至少包含所有p-1素数的最高次幂。
    经过二之后,我们也不需要手动指定B了。
    (会不会不满足条件的B1,也使得$a \equiv 1 (mod p)$?这样我们就不能累积并检验了。不会!$2^{B1} \equiv 2^{\left \lfloor \frac{B1}{p-1} \right \rfloor + B1 mod (p-1)} (mod p) \equiv 2^{B1 mod (p-1)} \not \equiv 1(mod p)$

    import math
    n = 11461532818525251775869994369956628325437478510485272730419843320517940601808597552925629451795611990372651568770181872282590309894187815091191649914833274805419432525386234876477307472337026966745408507004000948112191973777090407558162018558945596691322909404307420094584606103206490426551745910268138393804043641876816598599064856358266650339178617149833032309379858059729179857419751093138295863034844253827963
    
    prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997];
    
    l = 0
    r = n
    squ = 0
    while l <= r:
        mid = (l+r) / 2
        if mid ** 2 > n:
            r = mid-1
        else:
            l = mid+1
            squ = max(mid, squ)
    
    # B is equal or less than sqrt(n)
    B = squ
    
    def gcd(a, b):
        if b == 0:
            return a
        return gcd(b, a%b)
    
    a = 2
    for a in prime:
        for i in prime:
            # 1 to highest exponent of each prime
            for j in range(1, int(math.log(B)/math.log(2))):
                a = pow(a, i, n)
                y = gcd(a-1, n)
                if y != 1:
                    print y
                    exit(0)
    

    解出9584834244487474725040608615807950187463557335614460164427946005333954173610613…
    另一个素因子也能解出来了

    总结:之所以这道题适合用Pollard p-1是因为p-1的素因子小于等于7,所以很快就解出来

    另外,python的一个库primefac可以用来分解因子

    Rail Fence Cipher

    栅栏密码,key为21时可以解出plaintext

    URE

    选择密文攻击
    $a’ \equiv a \times a \equiv g^{2r} (mod n)$
    $b’ \equiv b \times b \equiv h^{2r} (mod n)$
    $c’ \equiv a \times c \equiv g^{r+s} (mod n)$
    $d’ \equiv b \times d \equiv mh^{r+s} (mod n)$

    High-speed RSA Keygen

    from random import randrange
    import fractions
    
    
    def get_primes(n):
            numbers = set(range(n, 1, -1))
            primes = []
            while numbers:
                    p = numbers.pop()
                    primes.append(p)
                    numbers.difference_update(set(range(p*2, n+1, p)))
            return primes
    
    def egcd(a, b):
        if a == 0:
            return (b, 0, 1)
        else:
            g, y, x = egcd(b % a, a)
            return (g, x - (b // a) * y, y)
    
    def modinv(a, m):
        g, x, y = egcd(a, m)
        if g != 1:
            raise Exception('modular inverse does not exist')
        else:
            return x % m
    
    def miller_rabin(n, k):
        r, s = 0, n - 1
        while s % 2 == 0:
            r += 1
            s //= 2
        for _ in range(k):
            a = randrange(2, n - 1)
            x = pow(a, s, n)
            if x == 1 or x == n - 1:
                continue
            for _ in range(r - 1):
                x = pow(x, 2, n)
                if x == n - 1:
                    break
            else:
                return False
        return True
    
    
    ### main #################
    primes = get_primes(443)
    primes.sort()
    del primes[0]
    #print primes
    
    pi = 1;
    for x in primes:
            pi *= x
    print "pi=%X" % pi
    
    while True:
            kp = randrange(1, 2**12) + 2**12 + 2**13 + 2**14 + \
                            2**15 + 2**16 + 2**17 + 2**18 + 2**19
            print "kp=%X" % kp
    
            tp = 0
            while fractions.gcd(tp, pi) != 1:
                    print "trying..."
                    tp = randrange(1, 2**399);
            print "tp=%X" % tp
    
            p = kp * pi * 2**400 + tp
            print "p=%X" % p
            print "bitlength(p)=", len(bin(p))-2
    
            if miller_rabin(p, 40) == True:
                    break
    
    while True:
            kq = randrange(1, 2**12) + 2**12 + 2**13 + 2**14 + \
                            2**15 + 2**16 + 2**17 + 2**18 + 2**19
            print "kq=%X" % kq
    
            tq = 0
            while fractions.gcd(tq, pi) != 1:
                    print "trying..."
                    tq = randrange(1, 2**399);
            print "tq=%X" % tq
    
            q = kq * pi * 2**400 + tq
            print "q=%X" % q
            print "bitlength(q)=", len(bin(q))-2
    
            if miller_rabin(q, 40) == True:
                    break
    
    print "p=%X" % p
    print "q=%X" % q
    
    n = p * q
    print "n=%X" % n
    print "bitlength(n)=", len(bin(n))-2
    
    e = 2**16 + 1
    print "e=%X" % e
    #print "bitlength(e)=", len(bin(e))-2
    
    d = modinv(e, (p-1)*(q-1))
    print "d=%X" % d
    #print "bitlength(d)=", len(bin(d))-2
    
    m = 12354178254918274687189741234123412398461982374619827346981756309845712384198076
    print "m=%X" % m
    print "bitlength(m)=", len(bin(m))-2
    
    c = pow(m, e, n)
    print "c=%X" % c
    print "bitlength(c)=", len(bin(c))-2
    
    m2 = pow(c, d, n)
    print "m2=%X" % m2
    print "bitlength(m2)=", len(bin(m2))-2
    

    给了我们一个秘钥生成算法、密文还有公钥。
    公钥很大,硬破很困难。factdb也查不到。显然是算法有缺陷

    看随机数范围,相当大,这应该不是一个缺陷,millar_rabin是规范写的,应该也不是缺陷。

    $n=pq=(kp \cdot pi \cdot 2^{400} + tp) \cdot (kq \cdot pi \cdot 2^{400} + tq) = (kp \cdot kq \cdot)(pi \cdot 2^{400})^2 + (kp \cdot tq+kq \cdot tp)pi \cdot 2^{400} + tp \cdot tq$

    注意:
    $pi \cdot 2^{400} < 2^{1000}$
    $tp \cdot tq < 2^{800}$
    $kp \cdot tq + kq \cdot tp < 2^{420}$

    因此n可以看成$pi \cdot 2^{400}$进制数,总共有三位。我们可以分别求出这三位。即求出$kp \cdot kq$ 和 $kp \cdot tq + kq \cdot tp$ 和 $tp \cdot tq$
    利用着三个结果,和kp、kq变化范围很小的特点然后可以暴力求解,然后解方程可以得出所有数。
    解得
    q = 144245059483864997316184517203073096336312163518349447278779492969760750146161606776…
    p = 144299940222848685214153733110344660304144248927927225494186904499495592842937728938…

    n=0xA4E20DDB854955794E7ABF4AE40051C0FC30488C82AB93B7DD046C1CC094A54334C97E84B523BD3F79331EBEAF5249200D729A483D5B8D944D58DF18D2CA9401B1A1A6CDA8A3AC5C234A501794B76886C426FAC35AD9615ADAB5C94B58C03CCFFA891CE0156CBC14255F019617E40DE9124FBBE70D64CD823DCA870FF76B649320927628250D47DB8DFA9BBCE9964CB3FE3D1B69845BD6FA2E6938DDA1F109E5F4E4170C845B976BBD5121107642FC00606208F9BC83322532739BCFEAF706FB2AF985EBD9769C7FBD50ECBF55566BD44FB241F9FD2DE25069AA8C744F0558514F1E9C8E4297A4D4B25D9F2B7494B466C2E6E2834BA68C5C824215018368B4FB
    
    def get_primes(n):
        numbers = set(range(n, 1, -1))
        primes = []
        while numbers:
            p = numbers.pop()
            primes.append(p)
            numbers.difference_update(set(range(p*2, n+1, p)))
        return primes
    
    
    ### main #################
    primes = get_primes(443)
    primes.sort()
    del primes[0]
    #print primes
    
    pi = 1;
    for x in primes:
        pi *= x
    
    base = 2**400 * pi
    kpkq = n / (base ** 2)
    kqtp_p_kptq = (n%(base**2)) / base
    tptq = n % base
    
    for kp in range(1, 2**12):
        kp += 2**12 + 2**13 + 2**14 + 2**15 + 2**16 + 2**17 + 2**18 + 2**19
        if kpkq % kp != 0:
            continue
        kq = kpkq / kp
    
        C = kq * tptq
        A = kp
        B = -kqtp_p_kptq
    
        if A == 0:
            if -C % B != 0:
                continue
            tq = -C / B
        else:
            delta = B**2 - 4*A*C
            if delta < 0:
                continue
    
            l = 0
            r = delta
            squ = -1
    
            while l < r:
                mid = (l+r)/2
                sqr = mid ** 2
                if sqr == delta:
                    squ = mid
                    break
                elif sqr < delta:
                    l = mid + 1
                elif sqr > delta:
                    r = mid - 1
    
            if (squ - B) % 2*A != 0:
                continue
    
            tq = (squ - B) / (2*A)
    
        tp = tptq / tq
    
        p = kp * pi * 2**400 + tp
        q = kq * pi * 2**400 + tq
    
        if p * q - n == 0:
            print p, q
    

    为什么这个方法能够成功?下面用直观的(并且可能不完善的)方式来解释一下。有空的话,再来具体推算一下。

    H(p)和H(q)都是很大的,因为H(tp)、H(tq)很大。
    然而H(p|n)=H(kp)这是为什么呢。

    因为H(p|n) = H(kp,tp|n) = H(kp)。根据kp和n能算出tp。

    原因就是n能够还原出kpkq,kqtp_p_kptq,tptq。假设p不再这样计算,而是p=kp*pi+tp,q同理,那么是不能只根据一个数n,计算出这三个“系数”的。此时可以是因为加法仅仅相当于连接。

    应该参考经典的素数生成算法。上面分析的可能只是最表面的原因。

    Impossible Game

    题解里有提到100囚犯问题,是一个置换群上的概率问题,50次测试内成功求解概率30.7%。
    而这里的空间只有$2^{22}$,直接枚举即可,甚至不需要了解散列函数

    Hail Zeus

    海明码和矩阵螺旋交织器,都是通信系统的东西,要逆向求解明文。这道题不知道有什么意思,并不熟悉这些东西。

    文章目錄
    1. 1. Smooth As Silk
      1. 1.0.1. Pollard p-1因子分解法
      2. 1.0.2. 实际的Pollard p-1
  • 2. Rail Fence Cipher
  • 3. URE
  • 4. High-speed RSA Keygen
  • 5. Impossible Game
  • 6. Hail Zeus