Login to System

栈溢出,标志位覆盖

Kick Tort Teen

VBA宏,写了一个ELF文件

uagent

流量分析,useragent里的base64。用dshell或dpkt来分析。

DUMPED

dump文件,不需要用windbg来找,内存在dump文件里是原始字节,直接grep Sharif即可

WE LOST THE FASHION FLAG

解压缩

Android App

把.so里的那串hash输进去就可以了,脑残没有反应过来。

Asian Cheetah

LSB

dMd

按字节比较

SRM

按字节比较

Serial

已经忘了。。

SecCoding

换成string

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

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

由于发现不记录,思考就变得肤浅,于是重启了博客。

最近一个月做的事情

两场失败的Codeforce
SharifCTF
ZCTF
读完的几本书:Fortran、CUDA绿皮书、深入理解Nginx
图像细化算法的三个优化,数据测试和论文
Autodafe的bugfix和代码阅读
阅读去年ASC15的Gridding的并行异构的别的队伍的范例。
ASC16的不佳的尝试
还未录完的Turbomole 6.6破解教程
明天即将到来的Sharif的AI challenge

大概没有干别的事情了。

学习Intel练习课
Hands-on Lab: Optimize Your Code for the Latest Intel®
XeonTM Processors and Intel® Xeon PhiTM Coprocessor
using Intel® Parallel Studio XE for Linux*

Stage 1

暂时不用考虑MonteCarlo的原理。Stage 1先后使用了gcc和icpc,并没有显著的进步。给我们的练习是使用mkl的并行随机数生成器。其目的就是对比mkl和串行随机数生成器的效率。mkl历史悠久,具有很高的可靠性,我们优化的时候,首先应该考虑这种集成度高的方式。

Intel的Developer Zone上有在线的API文档,查阅很方便。

typedef std::tr1::mt19937                     ENG;    // Mersenne Twister
typedef std::tr1::normal_distribution<float> DIST;   // Normal Distribution
typedef std::tr1::variate_generator<ENG,DIST> GEN;    // Variate generator

这些声明替换为如下:

float myrand[RAND_N];
VSLStreamStatePtr stream;
vslNewStream(&stream, VSL_BRNG_MT19937, 777);

一开始的时候,我一次性生成了两重循环需要的所有随机数,没有发现OPT_NRAND_N已经达十亿。不得已,只能在内层循环外生成OPT_NRAND_N个随机数。

vsRngGaussian(VSL_RNG_METHOD_GAUSSIAN_ICDF,stream,RAND_N,myrand,0.0,1.0);

vRngGaussian有double版和float版,分别是vdRngGaussian和vsRngGaussian。

在外层循环外删掉stream。

vslDeleteStream(&stream);

链接的时候又遇到了障碍,需要的所有库都得链接。

icc ./MonteCarloStep1.cpp ./Driver.cpp -I/opt/intel/composerxe/mkl/include -L/opt/intel/composexe/mkl/lib/intel64 -lmkl_intel_lp64 -lmkl_intel_thread -lmkl_core -lmkl_lapack95_lp64 -liomp5 -lpthread -O2 -o MonteCarlo

结果如下:总算是完成了。

Monte Carlo European Option Pricinig in Single Precision
Pricing 32768 Option with path length of 262144.
Completed in 151.4866 seconds.
Computation rate - 216.3096.

对照答案,发现答案有一点问题,每一次蒙特卡洛的模拟的随机变量是相同的,这样我觉得貌似失去了重复实验的意义,不排除是我对蒙特卡洛的理解出了问题。但是在效率上,仅一次生成RAND_N个随机数,的确提高了速度。

Stage 2

这几种优化手段都是第一次见到。float常量后面加上f,区分float和double对应的数学函数,减少冗余计算,避免类型转换,利用intel的计算比较快的数学函数。我对照答案修改之后的运行结果:(不过不是在同一个集群,没有参照性)

Monte Carlo European Option Pricinig in Single Precision
Pricing 32768 Option with path length of 262144.
Completed in 33.9102 seconds.
Computation rate - 966.3183.

而不用我的这些优化(不明白为什么答案没有优化这些地方,也许是我搞错了),时间是77s

对照答案,不明白为什么有的float常量后面写了f,有的没有。把强制转换预处理计算了,或者去掉了。为什么有个地方没有使用exp2f。为什么要把除法拿出来?为什么有的冗余计算给提前了,有的(如(RISKFREE - 0.5 VOLATILITY VOLATILITY)*M_LOG2E)则没有?static_cast和普通类型转换的区别?

Stage 3

由于向量化是书上着重讲的部分,于是我先自己实验,再看步骤。

-vec-report=3显示内层循环被向量化了,外层没有
使用#pragma ivdep没有用
观察发现,貌似并没有数据依赖,于是#pragma simd,时间从原来的77s变成了57s
进行到这里,感觉对我来说,已经完成了向量化工作。。。于是看资料

原来此文把内核级优化的内容也放到了该vectorization小节里。继续自己做实验。

切片,由于L2 cache是256KB,而RAND_N是2^18,l_Random是float数组,float是4字节,切成4块刚好每一块装满L2 cache,对于每个opt,处理长度为RAND_N/4的pos区间,这样提高了命中率,还不至于使内层循环并行度过低。时间从57s减少到了49s。
对齐,我有点犯晕,是否只有动态生成的内存才在这个问题上可控?
函数,这些函数应该都有对应的SIMD版本,会自动使用吧

又没有思路了。

reduction,如果不使用reduction,当数据量大了之后,可能出现竞争的问题,导致结果出错,reduction会给每一个线程一个副本,使用了reduction之后,外层循环不能向量化了,但是时间减为了14s。这是怎么回事?遂去掉了#pragma simd


照答案重做一遍
原始77s
向量对齐 声明数组时attribute((aligne(64)) float l_Random[RAND_N],第一维的首地址对齐。我想知道多维数组有什么不同。
然后#pragma vector aligned,声明向量已对齐
#pragma simd reduction(+:val) reduction(+:val2)用编译器自己向量化即可,不用openmp我还不明白openmp到底是干嘛的
#pragma unroll(4),展开了四次,因为里面加了一句话(因为max里计算了两次复杂表达式,手动展开了)总共四句
时间13s

Stage 4

计算是独立的,外层确实应该是可以向量化的
用openmp并行化外层循环
#pragma omp parallel for
平均时间1s

我不明白为什么可以用openmp而不能用simd。我确实需要复习openmp了,至少搞懂它到底是啥

Stage 5

mic的native模式,平均时间0.5s

明天继续补充,对照答案检查

我想自己做一点激进的实验,可是又没办法保证结果的正确,希望能找到什么资料讨论这个问题
当各个部件都熟悉了,问题会变成如何构建多级异构,如何使OpenMP、MPI等协调工作。