原文章:密码学笔记

RSA

一些基本知识:

RSA中几个用到的字母: P : 大质数p Q : 大质数q N : n=p*q φ(n) = φ(p) * φ(q) = (p − 1)(q − 1) = n − (p + q − 1) e : encryption key (public key) (又称加密指数) d : decryption key (private key) e对于φ(n)的模反元素 c : ciphertext m:message(m < n)

主要公式: $c ≡ m^e \pmod{n}$ $m ≡ c^d \pmod{n}$

欧拉函数:φ(n)是小于等于n的数中与n互质的数的数目。 欧拉函数是积性函数——若p,q互质,φ(pq)= φ(p) φ(q) 若p为质数,则φ(p)=p-1

同余定理:给定一个正整数m,如果两个整数a和b满足(a-b)能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m)。 性质: 1 反身性 a≡a (mod m) 2 对称性 若a≡b(mod m),则b≡a (mod m) 3 传递性 若a≡b (mod m),b≡c (mod m),则a≡c (mod m) 4 同余式相加 若a≡b (mod m),c≡d(mod m),则a+-c≡b+-d (mod m) 5 同余式相乘 若a≡b (mod m),c≡d(mod m),则ac≡bd (mod m)

模反元素:指有一个整数d,可以使得ed被φ(n)除的余数为1,即ed ≡ 1 (mod φ(n)),这个式子等于ed - 1 = kφ(n)

快速幂取模:python实现

def modexp(c,d,n):#等价于自带的pow(c,d,n)
    ret=1
    while d>0:
        c=c%n
        if d&1:
            ret=(ret*c)%n
        d>>=1
        c=(c*c)%n
    return ret

在linux上使用openssl解密的: 安装环境: sudo -i apt-get install libgmp3-dev sudo -i pip install gmpy sudo -i pip install pyasn1

rsatool.py:

#!/usr/bin/env python2
import base64, fractions, optparse, random
try:
    import gmpy
except ImportError as e:
    try:
        import gmpy2 as gmpy
    except ImportError:
        raise e

from pyasn1.codec.der import encoder
from pyasn1.type.univ import *

PEM_TEMPLATE = '-----BEGIN RSA PRIVATE KEY-----\n%s-----END RSA PRIVATE KEY-----\n'
DEFAULT_EXP = 65537

def factor_modulus(n, d, e):
    """
    Efficiently recover non-trivial factors of n
    See: Handbook of Applied Cryptography
    8.2.2 Security of RSA -> (i) Relation to factoring (p.287)
    http://www.cacr.math.uwaterloo.ca/hac/
    """
    t = (e * d - 1)
    s = 0

    while True:
        quotient, remainder = divmod(t, 2)

        if remainder != 0:
            break

        s += 1
        t = quotient

    found = False

    while not found:
        i = 1
        a = random.randint(1,n-1)

        while i <= s and not found:
            c1 = pow(a, pow(2, i-1, n) * t, n)
            c2 = pow(a, pow(2, i, n) * t, n)

            found = c1 != 1 and c1 != (-1 % n) and c2 == 1

            i += 1

    p = fractions.gcd(c1-1, n)
    q = (n / p)

    return p, q

class RSA:
    def __init__(self, p=None, q=None, n=None, d=None, e=DEFAULT_EXP):
        """
        Initialize RSA instance using primes (p, q)
        or modulus and private exponent (n, d)
        """

        self.e = e

        if p and q:
            assert gmpy.is_prime(p), 'p is not prime'
            assert gmpy.is_prime(q), 'q is not prime'

            self.p = p
            self.q = q
        elif n and d:   
            self.p, self.q = factor_modulus(n, d, e)
        else:
            raise ArgumentError('Either (p, q) or (n, d) must be provided')

        self._calc_values()

    def _calc_values(self):
        self.n = self.p * self.q

        if self.p != self.q:
            phi = (self.p - 1) * (self.q - 1)
        else:
            phi = (self.p ** 2) - self.p

        self.d = gmpy.invert(self.e, phi)

        # CRT-RSA precomputation
        self.dP = self.d % (self.p - 1)
        self.dQ = self.d % (self.q - 1)
        self.qInv = gmpy.invert(self.q, self.p)

    def to_pem(self):
        """
        Return OpenSSL-compatible PEM encoded key
        """
        return (PEM_TEMPLATE % base64.encodestring(self.to_der()).decode()).encode()

    def to_der(self):
        """
        Return parameters as OpenSSL compatible DER encoded key
        """
        seq = Sequence()

        for x in [0, self.n, self.e, self.d, self.p, self.q, self.dP, self.dQ, self.qInv]:
            seq.setComponentByPosition(len(seq), Integer(x))

        return encoder.encode(seq)

    def dump(self, verbose):
        vars = ['n', 'e', 'd', 'p', 'q']

        if verbose:
            vars += ['dP', 'dQ', 'qInv']

        for v in vars:
            self._dumpvar(v)

    def _dumpvar(self, var):
        val = getattr(self, var)

        parts = lambda s, l: '\n'.join([s[i:i+l] for i in range(0, len(s), l)])

        if len(str(val)) <= 40:
            print('%s = %d (%#x)\n' % (var, val, val))
        else:
            print('%s =' % var)
            print(parts('%x' % val, 80) + '\n')


if __name__ == '__main__':
    parser = optparse.OptionParser()

    parser.add_option('-p', dest='p', help='prime', type='int')
    parser.add_option('-q', dest='q', help='prime', type='int')
    parser.add_option('-n', dest='n', help='modulus', type='int')
    parser.add_option('-d', dest='d', help='private exponent', type='int')
    parser.add_option('-e', dest='e', help='public exponent (default: %d)' % DEFAULT_EXP, type='int', default=DEFAULT_EXP)
    parser.add_option('-o', dest='filename', help='output filename')
    parser.add_option('-f', dest='format', help='output format (DER, PEM) (default: PEM)', type='choice', choices=['DER', 'PEM'], default='PEM')
    parser.add_option('-v', dest='verbose', help='also display CRT-RSA representation', action='store_true', default=False)

    try:
        (options, args) = parser.parse_args()

        if options.p and options.q:
            print('Using (p, q) to initialise RSA instance\n')
            rsa = RSA(p=options.p, q=options.q, e=options.e)
        elif options.n and options.d:
            print('Using (n, d) to initialise RSA instance\n')
            rsa = RSA(n=options.n, d=options.d, e=options.e)
        else:
            parser.print_help()
            parser.error('Either (p, q) or (n, d) needs to be specified')

        rsa.dump(options.verbose)

        if options.filename:
            print('Saving %s as %s' % (options.format, options.filename))


            if options.format == 'PEM':
                data = rsa.to_pem()
            elif options.format == 'DER':
                data = rsa.to_der()

            fp = open(options.filename, 'wb')
            fp.write(data)
            fp.close()

    except optparse.OptionValueError as e:
        parser.print_help()
        parser.error(e.msg)

openssl 语句: 从公钥中读取e和n:openssl rsa -pubin -text -modulus -in warmup -in 【public.pem】 Rsatool.py生成指定的私钥:python rsatool.py -o 【private.pem】 -e 【65537】 -p 【123】-q 【123】 用私钥解密:openssl rsautl -decrypt -in 【flag.enc】 -inkey 【private.pem】

啥都知道类

只要了解RSA的基本运作原理就可以解密了。

例题:HCTF GAME 密码学教室入门(一)

题目描述:

p:0x9a724c6747de9eadccd33f4d60ada91754b8be8c65590cafe66f69a2f4afbfd359e47ca6fd2dbde8948062dc116bc574f4313ab99b2bb6d8ae47beaa0c1ebeddL

q:0x8c1c81cc005ce3dd6d684ebb88151dc0c53b1cef8a29b1cb8121860fb57d93117bf449aac4300dc6103ac6211c6f8ae68987d99aff0dd8967a4afa00f2116873L

e:0x190a000845e9c8c2059242835432326369aaf8c7ca85e685bba968b386155a91f1f7ca1019ff23d119222e1f0dfdeb0915d2e97601ef94bf15ca6d9211e984e9038f263f4984355c397ed22d67c26da6d31acfc4d599c70cba80859bee099e5a2dc3ab23aecf58f73f44d07318f70985c623d9612efefb15bf8dab77d5d54e85L

d:0x28b95b7e3159a851cbf537e007ae49864b7dbb93fc370a5L 

c:0x23091e42fa7609c73f1941b320fad6d2ff6e47be588d1623f970f1fee7abd221c9834b208f3c888902fe87ca76ec1e1363757d93c6e25c49f1c61c72b141c0b8848b54a117427d8e30eeab89694eb5f849cafecb0e5361b9b2b0e3f89e0fdbcc66a6aad4a1a4a85d828083a01a5d569b7eeb6f9151794453382b524aa52993f9L

不解释,用python写个脚本:

c=0x23091e42fa7609c73f1941b320fad6d2ff6e47be588d1623f970f1fee7abd221c9834b208f3c888902fe87ca76ec1e1363757d93c6e25c49f1c61c72b141c0b8848b54a117427d8e30eeab89694eb5f849cafecb0e5361b9b2b0e3f89e0fdbcc66a6aad4a1a4a85d828083a01a5d569b7eeb6f9151794453382b524aa52993f9
d=0x28b95b7e3159a851cbf537e007ae49864b7dbb93fc370a5
n=0x9a724c6747de9eadccd33f4d60ada91754b8be8c65590cafe66f69a2f4afbfd359e47ca6fd2dbde8948062dc116bc574f4313ab99b2bb6d8ae47beaa0c1ebedd * 0x8c1c81cc005ce3dd6d684ebb88151dc0c53b1cef8a29b1cb8121860fb57d93117bf449aac4300dc6103ac6211c6f8ae68987d99aff0dd8967a4afa00f2116873

m=pow(c,d,n)
print hex(m)[2:len(hex(m))-1].decode('hex')

flag:hgame{rsa_1s_v3ry_e4sy!}

吓唬人类

表面上是个RSA,其实根本没加密。

例题:HCTF GAME 密码学教室入门(四)

题目描述:

n: 0x81cfc71c44c83faf3c5242fa81ae2e533fc945f3bef30bc13323ea4a55b3debc11301c6a9ecb8f7ef92fa169b157435af728a145497f2cdf75b3007b9732da4c47d67683f09ae1edc8f698f5ec7549593d9f1d06adafae4ad09514928bf0367a2719f7c171580318690dafc6a3d5385b3516b769f529c0a055ce25e68bc21395L
e: 0x01
c: 0x6867616d657b7273615f31735f737469316c5f653473795f6e6f77217dL

注意到e=1,$c ≡ m^e * (\mod n)$,所以c ≡ m mod n,又因为n远大于c,所以m=c。

python:

print '6867616d657b7273615f31735f737469316c5f653473795f6e6f77217d'.decode('hex')

flag:hgame{rsa_1s_sti1l_e4sy_now!}

n能被工具快速分解类

两个常用的工具: 在线分解大质数(不一定都能成功分解):http://factordb.com/ windows工具:yafu

将n成功分解得到p,q。由p,q,e模反求得d。最后c,d,n求m。

例题:HCTF GAME 密码学教室进阶(五)

题目描述:

n = 0xee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f0228366aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca19bd54e39bbfa0d7a0e7c89d955b1c9fL

e = 0xe438fddb77f9bc2cf97185041e8a5ce8d0853cbfb657b940505870f0d3dfc0b723c5f7c8c9b940769f358397e275d00cce1cf760f9892a4b83ff90cbe513c6cc450258d02bcee33e499fb028c2b0d811bba22ef0c4fea314018d4943451ecdeb5d6e98bd5ed71ab7862a747f851c532aeae6c29f52c3f9be649a4142810ddb83015386fd035fcdc28059236135a9cce24fd650062067dcf43f5dcf24e15f132e9dca4ff68cc7637139dbdba276157f11e8af118d8dfae3f811a0377ba37555f9L

c = 0xbe864c22e69bd872541b7538b3c9797cf76afa2b2cac70c5a1a47fb6b6046daf345946d6e0eb299d12a7485ad9edaced28ef0b3169a22d1cba69c1e556ed2a69b6eca7e030f8cf61616faff4e063caf1a0668d4357594e7ff8887f00f61df5161e94f2197abcc2d34db666a34fa9e0f108c7937dc09b8e091ba2a4180f88f1b58229891bd619025f2c13f5758d7f4f6ac8f4d3f565449a730fef9ecee37f5409b801b554a30cfb42f69afc734b7709c5df6618e94e96b5d24a4b63cd1907296ae9bbd36084bad58c5e5cb3d275c953efc73aff595f36d92e182d6705fee14dabd29df53735132249d5935f8e780210359d67ab80ac2dfa29a88a5f585cbda8bbL

上factordb成功分解:

p=57970027
q=518629368090170828331048663550229634444384299751272939077168648935075604180676006392464524953128293842996441022771890719731811852948684950388211907532651941639114462313594608747413310447500790775078081191686616804987790818396104388332734677935684723647108960882771460341293023764117182393730838418468480006985768382115446225422781116531906323045161803441960506496275763429558238732127362521949515590606221409745127192859630468854653290302491063292735496286233738504010613373838035073995140744724948933839238851600638652315655508861728439180988253324943039367876070687033249730660337593825389358874152757864093

python模反:

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

e=0xe438fddb77f9bc2cf97185041e8a5ce8d0853cbfb657b940505870f0d3dfc0b723c5f7c8c9b940769f358397e275d00cce1cf760f9892a4b83ff90cbe513c6cc450258d02bcee33e499fb028c2b0d811bba22ef0c4fea314018d4943451ecdeb5d6e98bd5ed71ab7862a747f851c532aeae6c29f52c3f9be649a4142810ddb83015386fd035fcdc28059236135a9cce24fd650062067dcf43f5dcf24e15f132e9dca4ff68cc7637139dbdba276157f11e8af118d8dfae3f811a0377ba37555f9
p=57970027
q=518629368090170828331048663550229634444384299751272939077168648935075604180676006392464524953128293842996441022771890719731811852948684950388211907532651941639114462313594608747413310447500790775078081191686616804987790818396104388332734677935684723647108960882771460341293023764117182393730838418468480006985768382115446225422781116531906323045161803441960506496275763429558238732127362521949515590606221409745127192859630468854653290302491063292735496286233738504010613373838035073995140744724948933839238851600638652315655508861728439180988253324943039367876070687033249730660337593825389358874152757864093

d=modinv(e,(p-1)*(q-1))

print(d)

解得d:

d=12992115738506970540841649209878923850449850256938220982758830156637205612762035155282226327685920931284918421552064382225983813981014872739551419060382854503642590330353164882512391318500353428642008085236106734064291092981546537314015444185586142992938345877421430131346693442575558546897860918057428050551689499978084803855243769401293926790504832562795137719424038069153683270022346974394431002503195605976824311455435505098340184475009365363490476873157045002222791446505348037665177173433292491281964806330443250471290739357059963205400702250838949527437626820311142744601192434198274561316384331263223868573905

python解密:

c=0xbe864c22e69bd872541b7538b3c9797cf76afa2b2cac70c5a1a47fb6b6046daf345946d6e0eb299d12a7485ad9edaced28ef0b3169a22d1cba69c1e556ed2a69b6eca7e030f8cf61616faff4e063caf1a0668d4357594e7ff8887f00f61df5161e94f2197abcc2d34db666a34fa9e0f108c7937dc09b8e091ba2a4180f88f1b58229891bd619025f2c13f5758d7f4f6ac8f4d3f565449a730fef9ecee37f5409b801b554a30cfb42f69afc734b7709c5df6618e94e96b5d24a4b63cd1907296ae9bbd36084bad58c5e5cb3d275c953efc73aff595f36d92e182d6705fee14dabd29df53735132249d5935f8e780210359d67ab80ac2dfa29a88a5f585cbda8bb
d=12992115738506970540841649209878923850449850256938220982758830156637205612762035155282226327685920931284918421552064382225983813981014872739551419060382854503642590330353164882512391318500353428642008085236106734064291092981546537314015444185586142992938345877421430131346693442575558546897860918057428050551689499978084803855243769401293926790504832562795137719424038069153683270022346974394431002503195605976824311455435505098340184475009365363490476873157045002222791446505348037665177173433292491281964806330443250471290739357059963205400702250838949527437626820311142744601192434198274561316384331263223868573905
n=0xee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f0228366aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca19bd54e39bbfa0d7a0e7c89d955b1c9f
m=pow(c,d,n)
print hex(m)[2:len(hex(m))-1].decode('hex')

flag:hgame{1f_u_kn0w_p_q_1n_RSA_1t_is_easy___}

多个n有公约数分解类

还是对n的分解,只是和上面分解n的方法不同。这类题给了许多组MD5加密,有一个特点就是他们的q是相同的(p不同)。

运用gcd求出q,然后p=n/q求得p,然后老套路。

例题:HCTF GAME 进击的 Crypto [0]

题目描述(原题给了10组,我们只取前两组即可):

n is 28989197955870674811941817152881961892555962828020048566215146047714999804743571465320756664500939106612607504133407755470924915037883788416084924998195415611009578161228226056524027626453567996030151847302248848345942762209886902216532270655286303624781479379460319335849225128417295447574269158603952744753408534894136230960676590980945838733350143370605144754932401806068003166087495356366335014736018745371974324955357717635855207674309628146381030418983172039685916675081977078212813718313201568394044637347955108623458947913411108888733982376607647705302281273170230540579872437433435253235534772724624778056181
e is 65537
c is 14200655400630956617529154837540349350095534430543196299987252783320359338882400858000649938298574946882176873795065987640380185922571487987903069796872680567596754211592988768630729844485795253975027297563832927176988502771266530781452168489731952873297707254669904609865565861351429459102567318447934677565870915603816516557032164955329497823771897899211076176905132170360842951444390670253036307048815943908305457043184642918674003085039564350070641592716116089015861491205237748561298604957423077954850396167621218521884114394431799317165818964438359695744604198246716410783223931430682808151056020475306791729591

n is 29703811006265969568420235185761287243393105045336995893094671661145408859269297497044834735198371987472186770953203812235003929122122129964989222762478116003185582578013431109127657242169359697936471497781547555222392181694624446976869099519331688628488881595076878345856808384797954271081176432330698334469596003760530797898645529616535584139559768170011693043197581376652770244664582733792825511473683193195672487559140733668442863818306947800631472845430628311685792799840854080385208783178691512540436222290062939858472754953657763052720510548438848633979413756332920634307585878271699119574149435107725143578613
e is 65537
c is 4578343924026570978472440931890325318245466288503599188533732998304051832656861172828218449138067382663459418589454854723253403947485557649615240187148291946554256687236506349553390057789720132702311963022032912389266835192465297150080916409872411988524410949952643478505491642457481045586019802683635095575472601541635397816830552539347027587330022646372943452066068029168471475125499435879399193076604330172042202401974524486727842888375820659903161039255979785711025431762267505041403586092799995451754527655054098031095440553010856162282818464431911828926227552966047893177859591679867661412947560702301353393344

python分解n:

def gcd(a, b):
    if a < b:
        a, b = b, a

    while b != 0:
        temp = a % b
        a = b
        b = temp

    return a

n1 = 28989197955870674811941817152881961892555962828020048566215146047714999804743571465320756664500939106612607504133407755470924915037883788416084924998195415611009578161228226056524027626453567996030151847302248848345942762209886902216532270655286303624781479379460319335849225128417295447574269158603952744753408534894136230960676590980945838733350143370605144754932401806068003166087495356366335014736018745371974324955357717635855207674309628146381030418983172039685916675081977078212813718313201568394044637347955108623458947913411108888733982376607647705302281273170230540579872437433435253235534772724624778056181
n2 = 29703811006265969568420235185761287243393105045336995893094671661145408859269297497044834735198371987472186770953203812235003929122122129964989222762478116003185582578013431109127657242169359697936471497781547555222392181694624446976869099519331688628488881595076878345856808384797954271081176432330698334469596003760530797898645529616535584139559768170011693043197581376652770244664582733792825511473683193195672487559140733668442863818306947800631472845430628311685792799840854080385208783178691512540436222290062939858472754953657763052720510548438848633979413756332920634307585878271699119574149435107725143578613

p = gcd(n1,n2)

print p,"\n\n",n1 // p

解得n1下的p,q:

p=174020591931642579445639482520669966832472464887563376831648240313949745675620951449596182091422504516152964331753172816101258786500867442499980329622871605643244312864569190912571594622928685486487082899631190828171757188986378429230898856002204891580815930976676783807695195461562646917675429591266528741337 

q=166584871560820727096589642347689679565074855614352117551421403470172486999617714211766560053113999351102121040050712302652946259905787937498701699126275189937913458623225733035633870625681735432630656542758649284674875757423561657674667345174775248412119912423941445877761025122933990376999367161895532332413

老套路,模反求d,pow求m,不在写过程了,flag:hctf{I7_1s_d4nger0us_2_Sh4re_prim3}

低加密指数广播攻击类

看题目的话和上面很像,都是给了很多组的RSA,但这个类型有一个特点,就是e很小且相同。

如果选取的加密指数较低,并且使用了相同的加密指数给一个接受者的群发送相同的信息,那么可以进行广播攻击得到明文。

例题:HCTF GAME 进击的 Crypto [5]

题目描述:

n is 17551188754807399016342420221734945766749930201727412345251590531404061480740932995199065332987719183197199448336435851015540272155441486746027315107821340969105623451575872580170978368650593880274076025520453956378539766228430429142117994616985318963125739076826635459215114946159348678398268099389525414431618517743889314085714390430972783223270985688988995257770363117225472590084489120958397189130958462784532637453482182763505791720641422686749616216521724012108378680177131928438795893866425040489551258902610047574579899692834984999209528110849342042529825594061894238371591910354584305136154355365191215400149
e is 10
c is 4675182605549711347653299514777826238559040200527747810846901991433127025723361807211672208052862870258047285285949212515664278410499603829663266213968511493974766674071825225536665267049044619340378438531615983696406305841945756396579371794826265549929503043134668360055027276522368879193620937457881486509311711905722483187734650127796510808637890189952840971330768913946884525594627652458745930532219238258911608744112001798136394806004726472890838481881026716605743812674350955258003794590748258523929460446986020794445478076559635145181909093786617716473870604463315696183050495143502762614767485881979217577416

n is 21840437284422601584177601857355845296420300157767339109572377640408362726674561246210400400760474187121246893712480109326893614162779470768415282900713800983815570602250068673695044749932532689851310770087552524620857623442019428044482787965428075984951982104920901562456426672111590909100736209153905853035127247720276974050404663847547090362780729077829594684995979457326414947449083219461617302643392904522733812903141301332227357689517880801845510579518887472928083718826890369016944549160461428710615747001273521253638766267143341819170249648385341127263707417642925464809788975715332938666417316695941347477577
e is 10
c is 4586033930015814975553487614321341290358072960539564849589758593801587823414394351862074093343255479635303199078561905260793645869942622136164615776822867275172888812989071016687658023005838776181437470204528335444413852561895603377955959308318399246963213964044984235974352824060625970587119586612774322385216810264819426458641852166009899106655036755913322283219739741020656812034348404092018340277026844114272699170323014050087289715403989671918767712613414346320222745328800096615947138667139053339483278319521201983885423491905171167675501563556563890821756892474999549635650486944010346554641603343238490572689

n is 30015914133986758133105015082922460910471726819000479872816812806794140887209294393963063273377891203069864711466776200108173672428779293308320460116493040572826915020654293929241843686728296387400110062099074573009645563520805301899962344680821396200256042478539540675850427377958553324581371362112652752444824919601767821622038488365501031636558236126052654241662743070651213369566898998898634441261811655053789384588711547685939927721116404429914329081432990913321296964957260691148704710581681774562904924080813274984809940008968629515304859518629473284018332651831587916402539386242421630250537030688162675751761
e is 10
c is 12012575342366442210994368605032582129674485327006093552902983877957202172783938071684841031902396156899396879136388606996807608296316795628987877357547213450360953742947781700549506469226564975927361748596520878542651668963131021269851928174681007347771519569914690980744941965086762285630082781013781879511681353119117280354102271439057204066405072328422057721895983540492150402309552609035008272366176657384174081229798739099558539083074489500359062010164358300087124447037922844709870430218019673914305742939927888838599616520300011913022792060392260618046807788302643742874847024153198113792628046678578753632923

n is 18009718435825445649372629634867772247035138229493108362713630947680338354227735572070882390378632440365163117094233413520107070581908224239210969172094402760924055334584259678276505919418191623762998249724248379302786621689049107500760348303940112840664926231345646325964133281550765454719628161600475143792567309947330130747860125557547051843620899629217636918002929846463097841539446014019579830347356084080488561917440356848465812937246809018168582635191619622041079012450531811237168105634382108634135880887093525611263186925213027913337454706919754923593714509998062073450679720905569489304398625255143801533277
e is 10
c is 4249005911324898630458723491151576810198619078332972911420166645127258598519950448507640904379342817486426262054889199369385257812524759761245588973651578211291344326619317559377360319507727729535083143293335799588196976241949218037833747839545295030259115279668065886560417877204054684495047181117075603468672292268831273735956964067626837975218539840667641885621426607941950306330198897187683754687379611844278471572791816397950634388907233312117920634807989734011132718334334850592111651631323130933438007008983489782601827321396168104668493332626558911838721998173148508994771473224050827471186478106896949413831

n is 27090736422393991189249636552945539144039087911497773160371557650625344533254580764344628540515132884576739746597729079146155130899009238110101654711303800340566538298798432929136509923129089904647023409146264405964139002638684510681372633714179570768685640570209727600215295330846361754314973731753734397312932947433225732597524076563605729037998272803472953079912899867244318073144564355326520230078681106746670895643454939714423661018216469020021429142336238301775948794784776906058601395026463842070755547793192470653204078222827768950823747061655106900276571547680451953562314376913592896427730473091360051391129
e is 10
c is 18557109853898405974924769550105345673703067457537813607252151469933140760798378574244439559372100428971400070351173140348823652755825601433268832363575896137364288069984314151346137206115518309597389268875150549696376813277778514591532615794294637044626683931367510181612383681914421702261592233265455950023252407680604041046629667703207133146853618989187597749132650514038584280417791134426596848369417626039533740827554552117727501565841065077835398951826747855393552731497438983274201599740189743630949174610722118659019630964669901438690028070213710833335622573526403588737092869273969581607637522572757015237506

n is 22277916445389799876692954866506052125036892596099795492064670519272419621528759837318253665292779127861537748967309681231938516330289846519214661138299205082421968922350230121526530080908053297879027158545040193774647350499415863211113776785399848472712293535289113810322398103983587423306282629848367328743089145940536913390664697321526306054579656600439140061667264516070003507841618352122567379038304294976725469305215682426898731699093794930417366769249256999177339843020364367769712776225743916112170787273891225926246407201080202593858063362565931942590349178361085396799890148505959437244983447934838792051793
e is 10
c is 19221531342713801219971420455098666365124810169512711030444063942333694562364114172361552139176582476168134219937393468391346535097965763785916484012657401095066804857900941482772687159471483908107669892419626059680168762119954068288719303591498504050604628627299671160225276355636519961578118413913001058744164531470610279168723402009469959377794138715204862239973561494796213624769358906726186769711689962808937828553399403173762034548974335960107700638910231658795639167906700770120741974418495196827830462542130080965552102416180517600397897065113788279096066792533807104187868678848857780735334749865813019681909

n is 20851005254704933958354817552975190588383962843827122226904964048318053243049822277049715505735762051530592940514007687138882551369906711787133432792478447465241409449145625470766867280545673313710877827491010966285871747638401315338616986782370641881615238434667687936400955629642629748987839996011550408156162317201139746453148874558603034756902297066835592748562014100033050736650359512497633206350878620421058840864178654150287452573363251543090733404389037241843869379543719804499640600546216051812575335078292203435075056740907356476508423562893159958041443951220933694064510275964264723600894558623421819904501
e is 10
c is 2043866718532927301454127017521835945401727173760352488220517028498861777262807036566165189285730569375083406234212921588654098421290088269551352101830688429903600880691046607902396566775005694148315605616437713115424223594710186677844867273218443350479253279231960061845711898262461185970057002138523262952260834191169438764964758526877361442277664448596129451496415695776781879266732057920583336999766633938582656240607973759756021032489262381190762825081392613689817792764844409877116240223852376311404164963595040347176139494461319495285348608562589901671620063620688524249523700500144604558899272202564535295466

n is 21745680718194037861694569863678082853797244380310200176477643943644972463871360669070584682807703870684830948023158889780219716829353665600564791257912082043905122048004593803193375178269942973208249276102769671038752489438400731535367257356207098737711096953679231300720903502192144476519811856646400822239966219746455729409375771797064825552958482297097797911599808242875799342438899636328763766908154658738969614707377852147843953614178305416594819846812426828300689497046389665982817209315784313108617753052015326937047712513569322963102500122038505770232917473260057408981125469607573191926134043719437868156273
e is 10
c is 9018406452041117867927204674649220929160509942604290572303644183451237944912470236367308266319079349289625873447647200474598755869642999213142758825809522474810817609751187533346902667225032452694187162262683056445775455963994237202296104812386374636270188433521927503415507963477240913270879794141170568393025367891003921090015993944946205723601349149601256727433716155121883420271498265967234259068535172501445643752691860997480636101699340740265505767091920668218018002976632111256430655619061247292025654740889077014179258647084698229733160071306390020603636210736363198302407289195286953980520285032528614492926

n is 23257483042331781031320004066395973098539881870433034498180628292164825476845647596122889756396987220787263478778647199033523248861079487991256044473644515960559630792146394039814096408486541588067643811077716428015000310006227815563853161604153799667073262886506475792902392829571472354691875108497532721686076971371510238161060553858839091026451266521753830084143245517459861325880906431205328541736948784727909518259034781432825317588016829248046749554245422672923121452470552323438808591118050034108325754535134236727740460190849252647561826203675666601441506024780605194340777802389960180532831878689458096046821
e is 10
c is 17978671919734595201524186618868659656036765546673883938819333911564948587858876495802600244078413312462813938682090761599961604959609423010904187720748539707172853352540370208991902929002036775381503365170196838626379685712050728875172622632447875368166743751159775611642629408534890684109652648484868876710697249351895355111511281037497347712241242908563699707272843032773107477368790419109907271096351457526240471975122296483655337150130000812813081239181653384419149292970320991892073352340649237387406498087734708162094476092368665794350968924289259192893289337038201504066310173284757044802449600666007821509553

n is 27637004622327338030988157906180324667829916751358977640832765328645718696385482091781513197472066052101704131751158627239657425473994441143385613105528200215275110466263289952962400664293602133856809475295970322767309563273999319926150648399522508592521685688896842833243324070987594588134776515978198364901455727292006058624015674914131447232032058875410956114939938460192876157612457774033922125553271809409381181134668696682847583314698759337802814876161751333701826176655372126746717533228292189928645064111959824895679517476699556313948724818860906006774808944802984477517788391260149504822396276593451707118257
e is 10
c is 8597067880812456123669594978660135058668875834924201279924162761020137582662367704504988576614934966062323191666982943113656186783894245035267051756178331490881264629774635620179678000947771928854566239213498586078670870127924696459041295848474073879336501325437194563845414699360564571136683492426292766799121155041276162673427700999761055592609213603158576637212003771003996722743170543342885011289692845493598413965688949325670519743413071479057382602222055902593614159427186017797992219490308930116850084553033461316509457834436420821916094206010206229370273622681413176347187252950087428868295965528772832409316

m,e相同,不同的是c和n,有: $c_1 \equiv m^e \mod n_1$ $c_2 \equiv m^e \mod n_2$ $c_3 \equiv m^e \mod n_3$ ... $c_n \equiv m^e \mod n_n$

由中国剩余定理,得:

$c_x \equiv m^n \mod n_1n_2n_3\cdot\cdot\cdot n_n$

python解密得:

import gmpy

def my_parse_number(number):
    string = "%x" % number
    erg = []
    while string != '':
        erg = erg + [chr(int(string[:2], 16))]
        string = string[2:]
    return ''.join(erg)

def e_gcd(a, b):
    x,y = 0, 1
    lastx, lasty = 1, 0
    while b:
        a, (q, b) = b, divmod(a,b)
        x, lastx = lastx-q*x, x
        y, lasty = lasty-q*y, y
    return (lastx, lasty, a)

def chinese_remainder_theorem(items):
  N = 1
  for a, n in items:
    N *= n

  result = 0
  for a, n in items:
    m = N/n
    r, s, d = e_gcd(n, m)
    if d != 1:
      raise "Input not pairwise co-prime"
    result += a*s*m

  return result % N, N

e=10

n=[17551188754807399016342420221734945766749930201727412345251590531404061480740932995199065332987719183197199448336435851015540272155441486746027315107821340969105623451575872580170978368650593880274076025520453956378539766228430429142117994616985318963125739076826635459215114946159348678398268099389525414431618517743889314085714390430972783223270985688988995257770363117225472590084489120958397189130958462784532637453482182763505791720641422686749616216521724012108378680177131928438795893866425040489551258902610047574579899692834984999209528110849342042529825594061894238371591910354584305136154355365191215400149,21840437284422601584177601857355845296420300157767339109572377640408362726674561246210400400760474187121246893712480109326893614162779470768415282900713800983815570602250068673695044749932532689851310770087552524620857623442019428044482787965428075984951982104920901562456426672111590909100736209153905853035127247720276974050404663847547090362780729077829594684995979457326414947449083219461617302643392904522733812903141301332227357689517880801845510579518887472928083718826890369016944549160461428710615747001273521253638766267143341819170249648385341127263707417642925464809788975715332938666417316695941347477577,30015914133986758133105015082922460910471726819000479872816812806794140887209294393963063273377891203069864711466776200108173672428779293308320460116493040572826915020654293929241843686728296387400110062099074573009645563520805301899962344680821396200256042478539540675850427377958553324581371362112652752444824919601767821622038488365501031636558236126052654241662743070651213369566898998898634441261811655053789384588711547685939927721116404429914329081432990913321296964957260691148704710581681774562904924080813274984809940008968629515304859518629473284018332651831587916402539386242421630250537030688162675751761,18009718435825445649372629634867772247035138229493108362713630947680338354227735572070882390378632440365163117094233413520107070581908224239210969172094402760924055334584259678276505919418191623762998249724248379302786621689049107500760348303940112840664926231345646325964133281550765454719628161600475143792567309947330130747860125557547051843620899629217636918002929846463097841539446014019579830347356084080488561917440356848465812937246809018168582635191619622041079012450531811237168105634382108634135880887093525611263186925213027913337454706919754923593714509998062073450679720905569489304398625255143801533277,27090736422393991189249636552945539144039087911497773160371557650625344533254580764344628540515132884576739746597729079146155130899009238110101654711303800340566538298798432929136509923129089904647023409146264405964139002638684510681372633714179570768685640570209727600215295330846361754314973731753734397312932947433225732597524076563605729037998272803472953079912899867244318073144564355326520230078681106746670895643454939714423661018216469020021429142336238301775948794784776906058601395026463842070755547793192470653204078222827768950823747061655106900276571547680451953562314376913592896427730473091360051391129,22277916445389799876692954866506052125036892596099795492064670519272419621528759837318253665292779127861537748967309681231938516330289846519214661138299205082421968922350230121526530080908053297879027158545040193774647350499415863211113776785399848472712293535289113810322398103983587423306282629848367328743089145940536913390664697321526306054579656600439140061667264516070003507841618352122567379038304294976725469305215682426898731699093794930417366769249256999177339843020364367769712776225743916112170787273891225926246407201080202593858063362565931942590349178361085396799890148505959437244983447934838792051793,20851005254704933958354817552975190588383962843827122226904964048318053243049822277049715505735762051530592940514007687138882551369906711787133432792478447465241409449145625470766867280545673313710877827491010966285871747638401315338616986782370641881615238434667687936400955629642629748987839996011550408156162317201139746453148874558603034756902297066835592748562014100033050736650359512497633206350878620421058840864178654150287452573363251543090733404389037241843869379543719804499640600546216051812575335078292203435075056740907356476508423562893159958041443951220933694064510275964264723600894558623421819904501,21745680718194037861694569863678082853797244380310200176477643943644972463871360669070584682807703870684830948023158889780219716829353665600564791257912082043905122048004593803193375178269942973208249276102769671038752489438400731535367257356207098737711096953679231300720903502192144476519811856646400822239966219746455729409375771797064825552958482297097797911599808242875799342438899636328763766908154658738969614707377852147843953614178305416594819846812426828300689497046389665982817209315784313108617753052015326937047712513569322963102500122038505770232917473260057408981125469607573191926134043719437868156273,23257483042331781031320004066395973098539881870433034498180628292164825476845647596122889756396987220787263478778647199033523248861079487991256044473644515960559630792146394039814096408486541588067643811077716428015000310006227815563853161604153799667073262886506475792902392829571472354691875108497532721686076971371510238161060553858839091026451266521753830084143245517459861325880906431205328541736948784727909518259034781432825317588016829248046749554245422672923121452470552323438808591118050034108325754535134236727740460190849252647561826203675666601441506024780605194340777802389960180532831878689458096046821,27637004622327338030988157906180324667829916751358977640832765328645718696385482091781513197472066052101704131751158627239657425473994441143385613105528200215275110466263289952962400664293602133856809475295970322767309563273999319926150648399522508592521685688896842833243324070987594588134776515978198364901455727292006058624015674914131447232032058875410956114939938460192876157612457774033922125553271809409381181134668696682847583314698759337802814876161751333701826176655372126746717533228292189928645064111959824895679517476699556313948724818860906006774808944802984477517788391260149504822396276593451707118257]

c=[4675182605549711347653299514777826238559040200527747810846901991433127025723361807211672208052862870258047285285949212515664278410499603829663266213968511493974766674071825225536665267049044619340378438531615983696406305841945756396579371794826265549929503043134668360055027276522368879193620937457881486509311711905722483187734650127796510808637890189952840971330768913946884525594627652458745930532219238258911608744112001798136394806004726472890838481881026716605743812674350955258003794590748258523929460446986020794445478076559635145181909093786617716473870604463315696183050495143502762614767485881979217577416,4586033930015814975553487614321341290358072960539564849589758593801587823414394351862074093343255479635303199078561905260793645869942622136164615776822867275172888812989071016687658023005838776181437470204528335444413852561895603377955959308318399246963213964044984235974352824060625970587119586612774322385216810264819426458641852166009899106655036755913322283219739741020656812034348404092018340277026844114272699170323014050087289715403989671918767712613414346320222745328800096615947138667139053339483278319521201983885423491905171167675501563556563890821756892474999549635650486944010346554641603343238490572689,12012575342366442210994368605032582129674485327006093552902983877957202172783938071684841031902396156899396879136388606996807608296316795628987877357547213450360953742947781700549506469226564975927361748596520878542651668963131021269851928174681007347771519569914690980744941965086762285630082781013781879511681353119117280354102271439057204066405072328422057721895983540492150402309552609035008272366176657384174081229798739099558539083074489500359062010164358300087124447037922844709870430218019673914305742939927888838599616520300011913022792060392260618046807788302643742874847024153198113792628046678578753632923,4249005911324898630458723491151576810198619078332972911420166645127258598519950448507640904379342817486426262054889199369385257812524759761245588973651578211291344326619317559377360319507727729535083143293335799588196976241949218037833747839545295030259115279668065886560417877204054684495047181117075603468672292268831273735956964067626837975218539840667641885621426607941950306330198897187683754687379611844278471572791816397950634388907233312117920634807989734011132718334334850592111651631323130933438007008983489782601827321396168104668493332626558911838721998173148508994771473224050827471186478106896949413831,18557109853898405974924769550105345673703067457537813607252151469933140760798378574244439559372100428971400070351173140348823652755825601433268832363575896137364288069984314151346137206115518309597389268875150549696376813277778514591532615794294637044626683931367510181612383681914421702261592233265455950023252407680604041046629667703207133146853618989187597749132650514038584280417791134426596848369417626039533740827554552117727501565841065077835398951826747855393552731497438983274201599740189743630949174610722118659019630964669901438690028070213710833335622573526403588737092869273969581607637522572757015237506,19221531342713801219971420455098666365124810169512711030444063942333694562364114172361552139176582476168134219937393468391346535097965763785916484012657401095066804857900941482772687159471483908107669892419626059680168762119954068288719303591498504050604628627299671160225276355636519961578118413913001058744164531470610279168723402009469959377794138715204862239973561494796213624769358906726186769711689962808937828553399403173762034548974335960107700638910231658795639167906700770120741974418495196827830462542130080965552102416180517600397897065113788279096066792533807104187868678848857780735334749865813019681909,2043866718532927301454127017521835945401727173760352488220517028498861777262807036566165189285730569375083406234212921588654098421290088269551352101830688429903600880691046607902396566775005694148315605616437713115424223594710186677844867273218443350479253279231960061845711898262461185970057002138523262952260834191169438764964758526877361442277664448596129451496415695776781879266732057920583336999766633938582656240607973759756021032489262381190762825081392613689817792764844409877116240223852376311404164963595040347176139494461319495285348608562589901671620063620688524249523700500144604558899272202564535295466,9018406452041117867927204674649220929160509942604290572303644183451237944912470236367308266319079349289625873447647200474598755869642999213142758825809522474810817609751187533346902667225032452694187162262683056445775455963994237202296104812386374636270188433521927503415507963477240913270879794141170568393025367891003921090015993944946205723601349149601256727433716155121883420271498265967234259068535172501445643752691860997480636101699340740265505767091920668218018002976632111256430655619061247292025654740889077014179258647084698229733160071306390020603636210736363198302407289195286953980520285032528614492926,17978671919734595201524186618868659656036765546673883938819333911564948587858876495802600244078413312462813938682090761599961604959609423010904187720748539707172853352540370208991902929002036775381503365170196838626379685712050728875172622632447875368166743751159775611642629408534890684109652648484868876710697249351895355111511281037497347712241242908563699707272843032773107477368790419109907271096351457526240471975122296483655337150130000812813081239181653384419149292970320991892073352340649237387406498087734708162094476092368665794350968924289259192893289337038201504066310173284757044802449600666007821509553,8597067880812456123669594978660135058668875834924201279924162761020137582662367704504988576614934966062323191666982943113656186783894245035267051756178331490881264629774635620179678000947771928854566239213498586078670870127924696459041295848474073879336501325437194563845414699360564571136683492426292766799121155041276162673427700999761055592609213603158576637212003771003996722743170543342885011289692845493598413965688949325670519743413071479057382602222055902593614159427186017797992219490308930116850084553033461316509457834436420821916094206010206229370273622681413176347187252950087428868295965528772832409316]

data=[]
for i in range(len(c):
    data += [(c[i],n[i])]
x, n = chinese_remainder_theorem(data)
realnum = gmpy.mpz(x).root(e)[0].digits()
print my_parse_number(int(realnum))
#When e are small and same,it can be Hastad's broadcast attack.Maybe we won't have topic aboout RSA,but I wish you can explore it Non-stop.hctf{Hastad's_broadcast_attack_is_interesting}

得flag:hctf{Hastad's_broadcast_attack_is_interesting}

提供enc和pem文件类

这类题目需要用linux的openssl来解。

例题:Jarvis OJ Medium RSA

题目:http://pan.baidu.com/s/1kVwkEmb 密码:snl4

题目描述:flag.enc,pubkey.pem

linux下敲命令:openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem

这里写图片描述

得到:

e=65537
n=0xC2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD

factordb分解n:

q=275127860351348928173285174381581152299
p=319576316814478949870590164193048041239

模反(方法见前)得d:

d=10866948760844599168252082612378495977388271279679231539839049698621994994673

此时不能使用之前的方法解密,是解不出来的,还是需要用openssl,不过在这之前,需要用rsatool.py(在文章最前面,建议ctrl+F搜索)生成私钥。

linux下敲入(先把rsatool.py放在当前目录):python rsatool.py -o private.pem -e 65537 -p 275127860351348928173285174381581152299 -q 319576316814478949870590164193048041239

这里写图片描述

得到私钥以后用openssl解密:openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag.dec

这里写图片描述

flag:PCTF{256b_i5_m3dium}

Rabin 密码类

具体的看wiki吧:https://en.wikipedia.org/wiki/Rabin_cryptosystem

这个我也是第一次接触,慢慢啃下来的,应该会写的很唠叨(可能还有错误),也算是自己的笔记吧。

例题:Jarvis OJ Hard RSA

题目:http://pan.baidu.com/s/1nv4UcI1 密码:obbz

题目描述:flag.enc,pubkey.pem。1.不需要爆破。2.用你的数学知识解决此题。3.难道大家都不会开根号吗?

同上,先openssl,得到e和n:

e=2
n=0xC2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD

factordb分解n:

p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239

我们观察到e为2,提示用数学知识来解,所以应该是Rabin密码。

先写一下Rabin的加密方法:

p,q
n=p*q
p = {0,1,2 ... n-1}
取m∈p

c ≡ m^2 (mod n)

Rabin解密:

首先因为$c = m^2 \pmod{n}$

从而有$m_p = \sqrt{c} \pmod{p}$ 和 $m_q = \sqrt{c} \pmod{q}$

又因为二次剩余:

若p是奇质数且p不能整除d,则: 1.d是模p的二次剩余当且仅当:$d^{\frac{p-1}{2}} \equiv 1 \pmod{p}$ 2.d是模p的非二次剩余当且仅当:$d^{\frac{p-1}{2}} \equiv -1 \pmod{p}$

两遍同时乘上d,再开根号,得到:$\pm c^{\frac{p+1}{4}} \equiv \sqrt{c} \pmod{n}$

所以$m_p \equiv c^{\frac{p+1}{4}} \pmod p$ , $m_q \equiv c^{\frac{q+1}{4}} \pmod q$

然后根据中国剩余定理:

设正整数$m_1,m_2...m_k$两两互素,则同余方程组 $x \equiv a_1 \pmod{m_1}$ $x \equiv a_2 \pmod{m_2}$ $x \equiv a_3 \pmod{m_3}$ ... $x \equiv a_k \pmod{m_k}$

有整数解。并且在模$M = m_1 \cdot m_2 \cdot ... \cdot m_k$下的解是唯一的,解为 $x \equiv (a_1M_1M_1^{-1} + a_2M_2M_2^{-1} + ... + a_kM_kM_k^{-1}) \mod M$

其中$M_i = M / m_i$,而$M_i^{-1}$为$M_i$模$m_i$的逆元。

故我们得到: $r = (y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \mod n$ $-r = n - r$ $s= (y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \mod n$ $-s = n - s$

其中有一个为我们想要的明文m。

python解密:

import gmpy

def n2s(num):
    t = hex(num)[2:]
    if len(t) % 2 == 1:
        return ('0'+t).decode('hex')
    return t.decode('hex')

c = int(open('flag.enc','rb').read().encode('hex'),16)
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
n = p*q
r = pow(c,(p+1)/4,p)
s = pow(c,(q+1)/4,q)
a = gmpy.invert(p,q)
b = gmpy.invert(q,p)
x =(a*p*s+b*q*r)%n
y =(a*p*s-b*q*r)%n

print n2s(x%n)
print n2s((-x)%n)
print n2s(y%n)
print n2s((-y)%n)

最后在输出中找到flag:PCTF{sp3ci4l_rsa}

共模攻击类

如果在RSA的使用中使用了相同的模n对相同的明文m进行了加密,那么就可以在不分解n的情况下还原出明文m的值。

例题:Jarvis OJ Hard RSA

题目:http://pan.baidu.com/s/1jIfXHoM 密码:9fyr

题目描述:flag.enc1,flag.enc2,veryhardRSA.py

首先分析加密脚本,先判断下是否够512-11位,不够的随机补全。 然后就是使用相同的N,不同的e,加密相同的数据。所以想到了共模攻击。

即加密时有: $ c_1\equiv m^{e_1} \pmod{n}$ $ c_2\equiv m^{e_2} \pmod{n}$

如果$e_1,e_2$互质,即存在$s_1,s_2$使得: $ s_1e_1+s_2e_2=1 $

从而可以化简得到:$c_1^{s_1}c_2^{s_2}\equiv m$ $mod$ $n$

python脚本:

from gmpy import invert
n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
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)

c1 = int(open('flag.enc1', 'rb').read().encode('hex'),16)
c2 = int(open('flag.enc2', 'rb').read().encode('hex'),16)
e1 = 17
e2 = 65537
s = egcd(e1,e2)
s1 = s[1]
s2 = s[2]
if s1<0:
    s1 = - s1
    c1 = invert(c1, n)
elif s2<0:
    s2 = - s2
    c2 = invert(c2, n)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
print hex(m)[2:].decode('hex')

flag:PCTF{M4st3r_oF_Number_Th3ory}


数论相关

不好分类,只能这样写了。

例题:HCTF GAME 进击的 Crypto [4]

题目描述:python文件

import hashlib
from gmpy2 import mpz, invert

p = 190716027447646792844189733681358379327343061199369341384474902557309769682923254674220284045951117393868651638379541511185212421611653965460100979887725583476037189369599999668327299529542494009290049992057157747007152994025186591269943960410319186487203043168774653327128061548663247131284489765017
q = 930788704028200015275140127068138499329817310955
g = 220237156062724657086413463831954488565703875839368639153162645824259735475648417436812689270045835305613201869418328189101417845912386944695747737570415063979393239590022180767575736652824918336764694014421673518178065244519367602124516716571334763354973717129155502536345229391073998560517516716958
k = '???'
x = '???'

def data_to_int(s):
    return int(s.encode('hex'), 16)

def SHA1(data):
    return data_to_int(hashlib.sha1(data).hexdigest())

def encrypt(data, p, q, g, x, k):
    r = pow(g, k, p) % q
    s = (invert(k, q) * (SHA1(data) + x * r)) % q
    return (r, s)

data1 = "guest"
data2 = "admin"
(r1, s1) = encrypt(data1, p, q, g, x, k)
(r2, s2) = encrypt(data2, p, q, g, x, k)

print SHA1(data1)
print SHA1(data2)
print s1
print s2
print r1
print r2

"""
427262976273228083221871998313131945010029561209591706262118913937489577133576413685540380226864
835940898148680488372488685713345793755099380413493862399556052721366535745667186387858109315383
618159893787048300752592802884467155388759696698
659836539307844663175437862395252943516139307036
568752653628483014849549142909331362115254788206
568752653628483014849549142909331362115254788206
"""

def getflag(data):
    print 1
    if data == "getflag":
        (r, s) = encrypt(data, p, q, g, x, k)
        flag = "hctf{" + str(s % r) + "}"
        print flag

这里我做一个小小的改动,把gmpy2库改成gmpy,我的linux不知怎的就是装不上gmpy2,就拿gmpy将就一下,反正也能做题,如果有大佬知道怎么装请务必告诉我谢谢。

顺便说一下,我查资料的时候看到一种叫DSA的加密算法和他好像,虽然不知道这是不是DSA。

先观察加密函数: $r = ( g^k \mod p) \mod q$ $s = (invert(k, q) * (SHA1(data) + x * r)) \mod q$ 其中invert函数是求逆元。

题中给了两组加密,说明只用一组来暴力跑肯定是不科学的。如果从r入手肯定是暴力了,所以我从s入手。

两组的s相减可以发现:

$s2 - s1 = (invert(k,q) * (sha2-sha1)) \mod q$

消掉了其中的xr。我们记s = s2 - s1,sha = sha2 - sha1。 得到:$s = (y * sha) \mod q$ 其中:$ky \mod q = 1$ 因此我们两边乘k,化简得到:$k = (sha ÷s) \mod q$ 在python中利用gmpy的divm(sha,s,q)解出k。

对原始的s式子两边乘k,除r得到: $\frac{s1 * k}{r} = (\frac{sha1}{r} + x ) \mod q$

从而化简得到:$x = ((\frac{s1 * k}{r} \mod q) - (\frac{sha1}{r} \mod q)) \mod q$

在python中利用gmpy的(divm(s1*k,r,q) - divm(sha1,r,q)) % q解出k。

以下为完整的python解密代码:

import hashlib
from gmpy import mpz, invert,divm

p = 190716027447646792844189733681358379327343061199369341384474902557309769682923254674220284045951117393868651638379541511185212421611653965460100979887725583476037189369599999668327299529542494009290049992057157747007152994025186591269943960410319186487203043168774653327128061548663247131284489765017
q = 930788704028200015275140127068138499329817310955
g = 220237156062724657086413463831954488565703875839368639153162645824259735475648417436812689270045835305613201869418328189101417845912386944695747737570415063979393239590022180767575736652824918336764694014421673518178065244519367602124516716571334763354973717129155502536345229391073998560517516716958
sha1 = 427262976273228083221871998313131945010029561209591706262118913937489577133576413685540380226864
sha2 = 835940898148680488372488685713345793755099380413493862399556052721366535745667186387858109315383
s1 = 618159893787048300752592802884467155388759696698
s2 = 659836539307844663175437862395252943516139307036
r = 568752653628483014849549142909331362115254788206
s = s2 - s1
sha = sha2 - sha1

k = divm(sha,s,q)
x = (divm(s1*k,r,q) - divm(sha1,r,q)) % q

def data_to_int(s):
    return int(s.encode('hex'), 16)

def SHA1(data):
    return data_to_int(hashlib.sha1(data).hexdigest())

def encrypt(data, p, q, g, x, k):
    r = pow(g, k, p) % q
    s = (invert(k, q) * (SHA1(data) + x * r)) % q
    return (r, s)

def getflag(data):
    print 1
    if data == "getflag":
        (r, s) = encrypt(data, p, q, g, x, k)
        flag = "hctf{" + str(s % r) + "}"
        print flag

getflag("getflag")

解得flag:hctf{88169191231439818447681393510021281730269252095}


CBC

CBC字节翻转攻击

原理见:http://www.tuicool.com/articles/vEVFZz

例题:HCTF GAME explorer的奇怪番外5

题目描述:

咱们继续做密码学:) 这次的内容和块加密算法的块加密模式有关 这次我们来试试密码学中对Cipher Block Chaining (CBC)的一种常见攻击手段——CBC字节翻转攻击。 这里是服务器端源代码。 nc 121.42.25.113 20002

源码我贴在这里:

#! /usr/bin/python
import os
from Crypto.Cipher import AES
from Crypto import Random

def checkPad(data):
    num = ord(data[-1])
    if num < 1 or num > 16:
        print "decrypt error"
        return "null:null"
    for i in xrange(1,num+1):
        if data[-i] != chr(num):
            print "decrypt error"
            return "null:null"
    return data[:-num]


def signin():
    token = raw_input("give me you token:")
    iv = token[:32].decode('hex')
    cipherText = token[32:].decode('hex')
    aes = AES.new(key,AES.MODE_CBC,iv)
    plainText = aes.decrypt(cipherText)
    t = checkPad(plainText).split(':')
    if len(t) != 2:
        print "you are not admin"
        return 
    name,passwd = t
    if name == 'admin' and passwd == 'alvndasjncakslbdvlaksdn':
        print flag
    elif name == 'null' and passwd == 'null':
        return
    else:
        print "you are not admin"

def signup():
    print "sorry singup is close"

rand = Random.new() #use crypto safe random
for name in os.listdir('.'):
    if 'flag' in name:
        fp = open(name)
        flag,key = fp.readlines()
        fp.close()
        break

flag = flag.strip()
key = key.strip().decode('hex')
welcome = '''
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
         welcome to explorer's strange crypto
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
'''
menu = '''
what do you want to do?
1.sign in 
2.sing up
'''

print welcome

while True:
    print menu,
    choose = raw_input('enter you choose:')
    if choose == '1':
        signin()
    elif choose == '2':
        signup()
    else:
        print "invalid choose"

首先,我们sign up,比如我提交的是bdmin,密码和原来一样,是 alvndasjncakslbdvlaksdn。得到了token:

dbc290e4acefd383cd4bb93a0ee020e6169513e29fd7e5452f955b945cab77cf3348a76d1ea5cfc9278c8e2ad3539498

观察程序源码可知,前面的16位(decode之后)是iv:

def signin():
    token = raw_input("give me you token:")
    iv = token[:32].decode('hex')
    cipherText = token[32:].decode('hex')
    aes = AES.new(key,AES.MODE_CBC,iv)
    plainText = aes.decrypt(cipherText)
    name,passwd = checkPad(plainText).split(':')
    if name == 'admin' and passwd == 'alvndasjncakslbdvlaksdn':
        print flag
    else:
        print "you are not admin"

CBC是16位一组进行加密的,因此我们编写代码在改变iv的情况下把bdmin改成admin:

a='dbc290e4acefd383cd4bb93a0ee020e6169513e29fd7e5452f955b945cab77cf3348a76d1ea5cfc9278c8e2ad3539498'
b=a.decode('hex')
b=list(b)
b[0] = chr(ord(b[0]) ^ ord('b') ^ ord('a'))
b = ''.join(b)
c=b.encode('hex')
print c

得到构造的token:

d8c290e4acefd383cd4bb93a0ee020e6169513e29fd7e5452f955b945cab77cf3348a76d1ea5cfc9278c8e2ad3539498

提交得到flag: hctf{cRypT0_ls_1nteRestlng!}

padding oracle attack

具体原理见:http://blog.zhaojie.me/2010/10/padding-oracle-attack-in-detail.html

例题:HCTF GAME explorer的奇怪番外6

题目描述:

这次的内容还是和块加密算法的块加密模式有关 这次依然是密码学中对Cipher Block Chaining (CBC)的一种著名攻击手段——padding oracle attack。 这里是服务器端源代码。这次就没有注册功能啦。 nc 121.42.25.113 20003

代码在此:

#! /usr/bin/python
import os
from Crypto.Cipher import AES
from Crypto import Random

def checkPad(data):
    num = ord(data[-1])
    if num < 1 or num > 16:
        print "decrypt error"
        return "null:null"
    for i in xrange(1,num+1):
        if data[-i] != chr(num):
            print "decrypt error"
            return "null:null"
    return data[:-num]


def signin():
    token = raw_input("give me you token:")
    iv = token[:32].decode('hex')
    cipherText = token[32:].decode('hex')
    aes = AES.new(key,AES.MODE_CBC,iv)
    plainText = aes.decrypt(cipherText)
    t = checkPad(plainText).split(':')
    if len(t) != 2:
        print "you are not admin"
        return 
    name,passwd = t
    if name == 'admin' and passwd == 'alvndasjncakslbdvlaksdn':
        print flag
    elif name == 'null' and passwd == 'null':
        return
    else:
        print "you are not admin"

def signup():
    print "sorry singup is close"

rand = Random.new() #use crypto safe random
for name in os.listdir('.'):
    if 'flag' in name:
        fp = open(name)
        flag,key = fp.readlines()
        fp.close()
        break

flag = flag.strip()
key = key.strip().decode('hex')
welcome = '''
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
         welcome to explorer's strange crypto
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
'''
menu = '''
what do you want to do?
1.sign in 
2.sing up
'''

print welcome

while True:
    print menu,
    choose = raw_input('enter you choose:')
    if choose == '1':
        signin()
    elif choose == '2':
        signup()
    else:
        print "invalid choose"

因为网上大多是 Web 应用中的已知密文的攻击,而这道题是已知明文的攻击。不过大同小异。

这里写图片描述

如果我们先随便选取一段密文,根据这种攻击的思想跑出相应的 IV,但是问题在于此时的明文不一定是我们想要的。我们知道 AES 解密后的中间值(即上图中的 Intermidiary Value)是不变的,对于同一段密文和 key 来说。假设我们之前跑出来的明文及 IV 分别为 m1、IV1,要求的明文及 IV 为 m2、IV2

$\begin{matrix} m1\ xor\ IV1 = Intermidiary\ Value \ m2\ xor\ IV2 = Intermidiary\ Value \ IV2 = Intermidiary\ Value\ xor\ m2 \end{matrix}$

也就是说我们用跑出来的 Intermidiary Value 和 想要的明文进行异或,就得得到符合要求的 IV,然后我们从最后一组 token 往前跑,因为这样就可以异或得到的 IV 作为前一组的密文

python脚本:

import time
import socket
import random

host = '121.42.25.113'
port = 20003
sk = socket.socket()
sk.connect((host,port))
time.sleep(0.5)
mes = sk.recv(1024)

msg1 = 'admin:alvndasjnc'.encode('hex')
msg2 = 'akslbdvlaksdn'.encode('hex') + '03' * 3
intermediary = list('-' * 32)
IV = '0' * 32

def sendData(IV, c):
    IV = ''.join(IV)
    sk.sendall('1\n')
    sk.recv(1024)
    sk.sendall(IV + c + '\n')
    time.sleep(0.01)
    mes = sk.recv(1024)
    return mes

def changeIV(IV, num):
    tmp = (32 - num)/2
    nextPad = tmp + 1
    print str(num + 1).zfill(2) + '-' + str(num + 2).zfill(2) + ': ',
    for i in range(1,tmp + 1):
        tmp2 = 32 - 2 * i
        IV[tmp2:tmp2+2] = hex(int(''.join(IV[tmp2:tmp2+2]),16) ^ tmp ^ nextPad)[2:].zfill(2)
    return ''.join(IV)

def changeMessageIV(IV, m):
    num = 1
    for i in range(30,-1,-2):
        IV[i:i+2] = hex(int(''.join(IV[i:i+2]),16) ^ 17 ^ int(''.join(m[i:i+2]),16))[2:].zfill(2)
        num += 1
    return ''.join(IV)

def run(m, c):
    IV = '0' * 32   
    num = 30
    while 1:
        if num < 0:
            return changeMessageIV(list(IV), list(m))
        for i in range(256):
            h = hex(i)[2:].zfill(2)
            IV = list(IV)
            IV[num:num+2] = h
            res = sendData(IV, c)
            if 'decrypt error' not in res:
                IV = changeIV(IV, num)
                print IV
                num -= 2
                break

def main():
    c = '0' * 32
    token2 = run(msg2,c)
    print 'The token 2 is ' + token2
    c = token2
    token1 = run(msg1,c)
    print 'The token 1 is ' + token1
    print sendData(token1,token2 + '0'*32)

if __name__ == '__main__':
    main()

自改的块加密

考块加密的基本知识以及Feistel结构。

例题:HCTF GAME explorer的奇怪番外3

题目描述:

密钥:explorer 密文:1fde6a7b2ff15d0abad691215ca5d470 交flag的时候记得加上hctf{}

加密代码(python):

from hashlib import sha256

def xor(a,b):
    return ''.join([chr(ord(i)^ord(j)) for i,j in zip(a,b)])

def HASH(data):
    return sha256(data).digest()[:8]

def bes_encrypt(subkeys, data):
    i = 0
    d1 = data[:8]
    d2 = data[8:]
    for i in subkeys:
       d1 = xor(xor(HASH(d2),i),d1)
       d1,d2 = d2,d1

    return d2 + d1

def key_schedule(key):
    subKeys = []
    subKey = key
    for i in xrange(16):
        subKey = HASH(subKey)
        subKeys.append(subKey)
    return subKeys

def bes(key,data):
    subKeys = key_schedule(key)
    return bes_encrypt(subKeys, data).encode('hex')

#the result  is "1fde6a7b2ff15d0abad691215ca5d470"
if __name__ == "__main__":
    print bes('explorer','??flag_is_here??')

用python写出解密函数:

# -*- coding: cp936 -*-
from hashlib import sha256

def xor(a,b):
    return ''.join([chr(ord(i)^ord(j)) for i,j in zip(a,b)])#简单的异或

def HASH(data):
    return sha256(data).digest()[:8]#取前8位

def bes_encrypt(subkeys, data):
    i = 0
    d1 = data[:8]
    d2 = data[8:]
    for i in subkeys:
       d1 = xor(xor(HASH(d2),i),d1)
       d1,d2 = d2,d1

    return d2 + d1

def key_schedule(key):
    subKeys = []
    subKey = key
    for i in xrange(16):
        subKey = HASH(subKey)
        subKeys.append(subKey)#len(subKeys)=16
    return subKeys

def bes(key,data):
    subKeys = key_schedule(key)
    return bes_encrypt(subKeys, data).encode('hex')

def bes_de(key,data):
    subKeys = reversed(key_schedule(key))
    return bes_decrypt(subKeys, data.decode('hex'))

def bes_decrypt(subkeys, data):
    i = 0
    d1 = data[8:]
    d2 = data[:8]
    for i in subkeys:
        d1,d2 = d2,d1
        d1 = xor(xor(HASH(d2),i),d1)
    return d1+d2

#the result  is "rEvers3_tHe_kEy!"
if __name__ == "__main__":
    print bes_de('explorer','1fde6a7b2ff15d0abad691215ca5d470')

加上flag{}得到最终的flag:flag{rEvers3_tHe_kEy!}


古典密码

古典密码编码方法归根结底主要有两种,即置换和代换。

把明文中的字母重新排列,字母本身不变,但其位置改变了,这样编成的密码称为置换密码。最简单的置换密码是把明文中的字母顺序倒过来,然后截成固定长度的字母组作为密文。

代换密码则是将明文中的字符替代成其他字符。

凯撒密码

凯撒密码是一种代换密码。明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。

如果有数字,则数字进行另外偏移量的偏移(可能与字母相同)。

例题:HCTF GAME 密码学教室入门(二)

题目描述:mlfrj{Hfjxfw_hnumjw_8x_ozxy_ktw_kzs}

你可以用JPK工具来解,也可以用python来解,比如我选择python。

a='mlfrj{Hfjxfw_hnumjw_8x_ozxy_ktw_kzs}'
for i in range(27):
    b = []
    for c in a:
        if c.isalpha() :
            c = chr(ord(c)-1)
            if c.isalpha() == 0:
                c = chr(ord(c)+26)
        b.append(c)

    a = ''.join(b)
    print a

输出为:

lkeqi{Geiwev_gmtliv_8w_nywx_jsv_jyr}
kjdph{Fdhvdu_flskhu_8v_mxvw_iru_ixq}
jicog{Ecguct_ekrjgt_8u_lwuv_hqt_hwp}
ihbnf{Dbftbs_djqifs_8t_kvtu_gps_gvo}
hgame{Caesar_cipher_8s_just_for_fun}
gfzld{Bzdrzq_bhogdq_8r_itrs_enq_etm}
feykc{Aycqyp_agnfcp_8q_hsqr_dmp_dsl}
edxjb{Zxbpxo_zfmebo_8p_grpq_clo_crk}
dcwia{Ywaown_yeldan_8o_fqop_bkn_bqj}
cbvhz{Xvznvm_xdkczm_8n_epno_ajm_api}
baugy{Wuymul_wcjbyl_8m_domn_zil_zoh}
aztfx{Vtxltk_vbiaxk_8l_cnlm_yhk_yng}
zysew{Uswksj_uahzwj_8k_bmkl_xgj_xmf}
yxrdv{Trvjri_tzgyvi_8j_aljk_wfi_wle}
xwqcu{Squiqh_syfxuh_8i_zkij_veh_vkd}
wvpbt{Rpthpg_rxewtg_8h_yjhi_udg_ujc}
vuoas{Qosgof_qwdvsf_8g_xigh_tcf_tib}
utnzr{Pnrfne_pvcure_8f_whfg_sbe_sha}
tsmyq{Omqemd_oubtqd_8e_vgef_rad_rgz}
srlxp{Nlpdlc_ntaspc_8d_ufde_qzc_qfy}
rqkwo{Mkockb_mszrob_8c_tecd_pyb_pex}
qpjvn{Ljnbja_lryqna_8b_sdbc_oxa_odw}
poium{Kimaiz_kqxpmz_8a_rcab_nwz_ncv}
onhtl{Jhlzhy_jpwoly_8z_qbza_mvy_mbu}
nmgsk{Igkygx_iovnkx_8y_payz_lux_lat}
mlfrj{Hfjxfw_hnumjw_8x_ozxy_ktw_kzs}
lkeqi{Geiwev_gmtliv_8w_nywx_jsv_jyr}

得到:hgame{Caesar_cipher_8s_just_for_fun} 再对数字进行一定的偏移,比如我们观察此时应该是'1s'。

flag:hgame{Caesar_cipher_1s_just_for_fun}

埃特巴什码

也是一种非常简单的以字母倒序排列作为特殊密钥的替换密码。

替换方法如下:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
ZYXWVUTSRQPONMLKJIHGFEDCBA

例题:暂无

比如有明文m = the quick brown fox jumps over the lazy dog 密文:c = gsv jfrxp yildm ulc qfnkh levi gsv ozab wlt

python脚本:

from string import maketrans,translate

map = maketrans('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz','ZYXWVUTSRQPONMLKJIHGFEDCBAzyxwvutsrqponmlkjihgfedcba')

m_or_c = 'gsv jfrxp yildm ulc qfnkh levi gsv ozab wlt'
print m_or_c.translate(map)
#the quick brown fox jumps over the lazy dog

rot类(5,13,18,47)

rot类其实就是特殊的凯撒密码。特殊在它具有可逆性,可以自我解密。加密和解密的函数相同,比如rot13,13是因为有26个字母,一个字母+13再+13以后就是它本身。

ROT5:只对数字进行编码,用当前数字往前数的第5个数字替换当前数字,例如当前为0,编码后变成5,当前为1,编码后变成6,以此类推顺序循环。

ROT13:只对字母进行编码,用当前字母往前数的第13个字母替换当前字母,例如当前为A,编码后变成N,当前为B,编码后变成O,以此类推顺序循环。

ROT18:这是一个异类,本来没有,它是将ROT5和ROT13组合在一起,为了好称呼,将其命名为ROT18。

ROT47:对数字、字母、常用符号进行编码,按照它们的ASCII值进行位置替换,用当前字符ASCII值往前数的第47位对应字符替换当前字符,例如当前为小写字母Z,编码后变成大写字母K,当前为数字0,编码后变成符号_。用于ROT47编码的字符其ASCII值范围是33-126,具体可参考ASCII编码。

例题:HCTF 2014 Entry

题目描述:57R9S980RNOS49973S757PQO9S80Q36P 听说丘比龙一口气能吃“13”个甜甜圈呢!

python解rot13:

from string import maketrans,translate

map = maketrans('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz','NOPQRSTUVWXYZABCDEFGHIJKLMnopqrstuvwxyzabcdefghijklm')

m_or_c = '57R9S980RNOS49973S757PQO9S80Q36P'
print m_or_c.translate(map)

得到57E9F980EABF49973F757CDB9F80D36C

md5解密得Qoobee

简单替换密码

简单换位密码(Simple Substitution Cipher)加密方式是以每个明文字母被与之唯一对应且不同的字母替换的方式实现的。和埃特巴什码的区别在于他的替换码不再是Z→A,而是乱序的,比如:

abcdefghijklmnopqrstuvwxyz
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
phqgiumeaylnofdxjkrcvstzwb

解这种密码我们可以用字频分析的方法(当密文足够长时),或者我们可以利用网站:http://quipqiup.com/

例题:暂无

比如我们有密文:

pmpafxaikkitprdsikcplifhwceigixkirradfeirdgkipgigudkcekiigpwrpucikceiginasikwduearrxiiqepcceindgmieinpwdfprduppcedoikiqiasafmfddfipfgmdafmfdteiki

扔进quipqiup中,解得明文:

again pierre was overtaken by the depression he so dreaded for three days after the delivery of his speech at the lodge he lay on a sofa at home receiving no one and going nowhere

希尔密码

希尔密码(Hill Cipher)是基于线性代数多重代换密码,由Lester S. Hill在1929年发明。每个字母转换成26进制数字:A=0, B=1, C=2…Z=25一串字母当成n维向量,跟一个n×n的矩阵相乘,再将得出的结果 MOD 26。

|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z| |-| |0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|

举例:我们有明文ACT,明文对应矩阵:

$\begin{pmatrix}0 \\ 2 \\ 19\end{pmatrix}$

我们的加密密钥为:GYBNQKURP,对应加密矩阵:

$\begin{pmatrix}6&24&1\\ 13&16&10\\ 20&17&15\end{pmatrix}$

计算过程:

$\begin{pmatrix}6&24&1\\ 13&16&10\\ 20&17&15\end{pmatrix}\begin{pmatrix}0\\ 2\\ 19\end{pmatrix} = \begin{pmatrix}67\\ 222\\ 319\end{pmatrix} \equiv \begin{pmatrix}15\\ 14\\ 7\end{pmatrix}\pmod{26}$

得到密文:POH

解密先求加密矩阵的逆矩阵,即解密矩阵:

$\begin{pmatrix}6&24&1\\ 13&16&10\\ 20&17&15\end{pmatrix}^{-1} \equiv \begin{pmatrix}8&5&10\\ 21&8&21\\ 21&12&8\end{pmatrix} \pmod{26}$

解密计算:

$\begin{pmatrix}8&5&10\\ 21&8&21\\ 21&12&8\end{pmatrix}\begin{pmatrix}15\\ 14\\ 7\end{pmatrix} \equiv \begin{pmatrix}260\\ 574\\ 539\end{pmatrix} \equiv \begin{pmatrix}0\\ 2\\ 19\end{pmatrix} \pmod{26}$

得到明文:ACT

例题:HCTF GAME 密码学教室进阶(六)

题目描述:

c:jchfecncvxogmtgqtqlqamqutqsgnniw
key:5 17 4 15
完成解密以后加上hgame{}作为flag

这题...手解嫌累,写代码我也不会写,只能找个在线解密:http://www.practicalcryptography.com/ciphers/hill-cipher/

总之扔进去就好了...

flag:hgame{haohaoxuexiandainihuiqiuniyuanma}

猪圈密码

是一种简单的替换密码。

这里写图片描述

应该都看得懂,不解释了。

栅栏密码

栅栏密码(Rail-fence Cipher)就是把要加密的明文分成N个一组,然后把每组的第1个字符组合,每组第2个字符组合…每组的第N(最后一个分组可能不足N个)个字符组合,最后把他们全部连接起来就是密文,这里以2栏栅栏加密为例。

例题:IDF 聪明的小羊

题目描述:

一只小羊跳过了栅栏,两只小样跳过了栅栏,一坨小羊跳过了栅栏... tn c0afsiwal kes,hwit1r g,npt ttessfu}ua u hmqik e {m, n huiouosarwCniibecesnren.

写个py脚本:

def decrypt(c = None, zu = 0, len = 0 ):
    m=''
    for i in range(zu):
        for j in range(len):
            m = m+c[i+zu*j]
    return m

c="tn c0afsiwal kes,hwit1r  g,npt  ttessfu}ua u  hmqik e {m,  n huiouosarwCniibecesnren."
for zu in range(1,len(c)):
    if len(c)%zu == 0:
        print decrypt(c,zu,len(c)/zu)

输出为可能的答案:

tn c0afsiwal kes,hwit1r  g,npt  ttessfu}ua u  hmqik e {m,  n huiouosarwCniibecesnren.
taastg su km uwbnnfl,1, sah ,hoCer s hrntf me usncecikw ptuuq  iaien0wei te} i{noris.
the anwser is wctf{C01umnar},if u is a big new,u can help us think more question,tks.

得flag:wctf{C01umnar}

培根密码

替换表(这是最常用的一套):

a   AAAAA   g     AABBA   n    ABBAA   t     BAABA
b   AAAAB   h     AABBB   o    ABBAB   u-v   BAABB
c   AAABA   i-j   ABAAA   p    ABBBA   w     BABAA
d   AAABB   k     ABAAB   q    ABBBB   x     BABAB
e   AABAA   l     ABABA   r    BAAAA   y     BABBA
f   AABAB   m     ABABB   s    BAAAB   z     BABBB

加密者需使用两种不同字体。准备好一篇包含相同AB字数的假信息后,即两种字体分别代表A型和B型。然后假信息中的每个字母按字体来决定其代表“A”还是“B”。

法兰西斯·培根另外准备了一种方法,其将大小写分别看作A与B。

例题:HCTF GAME 我是一个没节操的misc题目

题目描述:flag的其中一段加密后是: wOsHiShUIWOZAINAaaAa_zHeShIsHENMEgUI_SHuinENggaOSuwo}

按照大写A,小写B,首先得到: BABABABAAAAAAAAABBAB_BABABABAAAAABAA_AABBBAABBBAABBB}

查表得到:xiao_xie_hhh}

维吉尼亚密码

等我整理。。。

暂时先扔个网址:http://quipqiup.com/


代码混淆加密

aaencode

aaencode可以将JS代码转换成常用的网络表情,也就是我们说的颜文字js加密。

在线加密:http://utf-8.jp/public/aaencode.html

比如我们有代码:

゚ω゚ノ= /`m´)ノ ~┻━┻   //*´∇`*/ ['_']; o=(゚ー゚)  =_=3; c=(゚Θ゚) =(゚ー゚)-(゚ー゚); (゚Д゚) =(゚Θ゚)= (o^_^o)/ (o^_^o);(゚Д゚)={゚Θ゚: '_' ,゚ω゚ノ : ((゚ω゚ノ==3) +'_') [゚Θ゚] ,゚ー゚ノ :(゚ω゚ノ+ '_')[o^_^o -(゚Θ゚)] ,゚Д゚ノ:((゚ー゚==3) +'_')[゚ー゚] }; (゚Д゚) [゚Θ゚] =((゚ω゚ノ==3) +'_') [c^_^o];(゚Д゚) ['c'] = ((゚Д゚)+'_') [ (゚ー゚)+(゚ー゚)-(゚Θ゚) ];(゚Д゚) ['o'] = ((゚Д゚)+'_') [゚Θ゚];(゚o゚)=(゚Д゚) ['c']+(゚Д゚) ['o']+(゚ω゚ノ +'_')[゚Θ゚]+ ((゚ω゚ノ==3) +'_') [゚ー゚] + ((゚Д゚) +'_') [(゚ー゚)+(゚ー゚)]+ ((゚ー゚==3) +'_') [゚Θ゚]+((゚ー゚==3) +'_') [(゚ー゚) - (゚Θ゚)]+(゚Д゚) ['c']+((゚Д゚)+'_') [(゚ー゚)+(゚ー゚)]+ (゚Д゚) ['o']+((゚ー゚==3) +'_') [゚Θ゚];(゚Д゚) ['_'] =(o^_^o) [゚o゚] [゚o゚];(゚ε゚)=((゚ー゚==3) +'_') [゚Θ゚]+ (゚Д゚) .゚Д゚ノ+((゚Д゚)+'_') [(゚ー゚) + (゚ー゚)]+((゚ー゚==3) +'_') [o^_^o -゚Θ゚]+((゚ー゚==3) +'_') [゚Θ゚]+ (゚ω゚ノ +'_') [゚Θ゚]; (゚ー゚)+=(゚Θ゚); (゚Д゚)[゚ε゚]='\\'; (゚Д゚).゚Θ゚ノ=(゚Д゚+ ゚ー゚)[o^_^o -(゚Θ゚)];(o゚ー゚o)=(゚ω゚ノ +'_')[c^_^o];(゚Д゚) [゚o゚]='\"';(゚Д゚) ['_'] ( (゚Д゚) ['_'] (゚ε゚+(゚Д゚)[゚o゚]+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ ((o^_^o) +(o^_^o))+ ((o^_^o) +(o^_^o))+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ (゚ー゚)+ (゚Θ゚)+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ ((o^_^o) +(o^_^o))+ ((o^_^o) - (゚Θ゚))+ (゚Д゚)[゚ε゚]+(゚ー゚)+ (c^_^o)+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ (゚ー゚)+ ((o^_^o) +(o^_^o))+ (゚Д゚)[゚ε゚]+(゚ー゚)+ (c^_^o)+ (゚Д゚)[゚ε゚]+((゚ー゚) + (o^_^o))+ ((゚ー゚) + (゚Θ゚))+ (゚Д゚)[゚ε゚]+(゚ー゚)+ (c^_^o)+ (゚Д゚)[゚ε゚]+(゚ー゚)+ ((o^_^o) - (゚Θ゚))+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ (゚ー゚)+ (o^_^o)+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ ((o^_^o) +(o^_^o))+ (゚ー゚)+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ (゚ー゚)+ ((o^_^o) +(o^_^o))+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ ((゚ー゚) + (o^_^o))+ (o^_^o)+ (゚Д゚)[゚ε゚]+((o^_^o) +(o^_^o))+ ((o^_^o) - (゚Θ゚))+ (゚Д゚)[゚ε゚]+((o^_^o) +(o^_^o))+ (o^_^o)+ (゚Д゚)[゚ε゚]+((o^_^o) +(o^_^o))+ (o^_^o)+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ ((゚ー゚) + (o^_^o))+ ((゚ー゚) + (゚Θ゚))+ (゚Д゚)[゚ε゚]+(゚ー゚)+ ((o^_^o) - (゚Θ゚))+ (゚Д゚)[゚ε゚]+((゚ー゚) + (o^_^o))+ (o^_^o)+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ (゚ー゚)+ (゚Θ゚)+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ ((゚ー゚) + (゚Θ゚))+ (゚ー゚)+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ (゚ー゚)+ ((゚ー゚) + (゚Θ゚))+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ ((o^_^o) +(o^_^o))+ ((o^_^o) - (゚Θ゚))+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ ((o^_^o) +(o^_^o))+ (゚ー゚)+ (゚Д゚)[゚ε゚]+((゚ー゚) + (゚Θ゚))+ (c^_^o)+ (゚Д゚)[゚ε゚]+(゚ー゚)+ ((o^_^o) - (゚Θ゚))+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ (゚ー゚)+ ((o^_^o) +(o^_^o))+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ ((゚ー゚) + (゚Θ゚))+ (゚ー゚)+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ (゚ー゚)+ (゚Θ゚)+ (゚Д゚)[゚ε゚]+(゚Θ゚)+ (゚ー゚)+ ((゚ー゚) + (o^_^o))+ (゚Д゚)[゚ε゚]+((゚ー゚) + (o^_^o))+ ((゚ー゚) + (o^_^o))+ (゚Д゚)[゚ε゚]+(゚ー゚)+ ((o^_^o) - (゚Θ゚))+ (゚Д゚)[゚ε゚]+((゚ー゚) + (゚Θ゚))+ (゚Θ゚)+ (゚Д゚)[゚o゚]) (゚Θ゚)) ('_');

解密方法就是在把代码后面的('_');去掉,然后在浏览器控制台上跑一下。

得到:

function anonymous() {
    var f = "ctf{233}";alert("flag?")
}

JSfuck

和上面类似。

在线加密:http://www.jsfuck.com/

解法同上,把最后一个()去掉。

jother

和上面类似。

在线加密:http://tmxk.org/jother/

解法同上,把最后一个()去掉。

brainfuck

Brainfuck是一种极小化的计算机语言,按照”Turing complete(完整图灵机)”思想设计的语言,它的主要设计思路是:用最小的概念实现一种“简单”的语言,BrainF**k 语言只有八种符号,所有的操作都由这八种符号(> < + - . , [ ])的组合来完成。

在线加解密:https://www.splitbrain.org/services/ook

密文:

+++++ ++++[ ->+++ +++++ +<]>+ +++++ +++++ +++++ ++.<+ +++[- >++++ <]>+.
<+++[ ->--- <]>-- ---.< ++++[ ->+++ +<]>+ ++++. <++++ ++++[ ->--- -----
<]>-- ----- --.+. ..<++ +++++ +[->+ +++++ ++<]> +++++ +++++ .<

不解释,直接扔进去就好了。

明文:ctf{2333}


编码类

base/32/64等

先说base16,其实就是hex,对,你没有看错。

比如有加密:

774F73486953685549574F5A41494E41616141615F7A48655368497348454E4D456755495F534875696E454E6767614F5375776F7D

直接在python里用decode('hex')就能解出明文。


base32:

有如下编码映射表:

Value Symbol Value Symbol Value Symbol Value Symbol
0 A 9 J 18 S 27 3
1 B 10 K 19 T 28 4
2 C 11 L 20 U 29 5
3 D 12 M 21 V 30 6
4 E 13 N 22 W 31 7
5 F 14 O 23 X
6 G 15 P 24 Y
7 H 16 Q 25 Z
8 I 17 R 26 2 pad =

只用到了A~Z和2~7。


base64:

|Value|Symbol|Value|Symbol|Value|Symbol|Value|Symbol| |--| |0|A|17|R|34|i|51|z| |1|B|18|S|35|j|52|0| |2|C|19|T|36|k|53|1| |3|D|20|U|37|l|54|2| |4|E|21|V|38|m|55|3| |5|F|22|W|39|n|56|4| |6|G|23|X|40|o|57|5| |7|H|24|Y|41|p|58|6| |8|I|25|Z|42|q|59|7| |9|J|26|a|43|r|60|8| |10|K|27|b|44|s|61|9| |11|L|28|c|45|t|62|+| |12|M|29|d|46|u|63|/| |13|N|30|e|47|v||| |14|O|31|f|48|w||| |15|P|32|g|49|x||| |16|Q|33|h|50|y|pad|=|

解base64直接用python的base64模块就行,不会的用在线解密也可以,玩re的需要去看看base64的加密函数怎么写,逆向时可能会遇到。

莫尔斯电码

对应表:

字符 电码 字符 电码 字符 电码 字符 电码 字符 电码
A .- N -. . .-.-.- + .-.-. 1 .- - - -
B -... O - - - , - -..- - _ ..- -.- 2 ..- - -
C -.-. P .- -. : - - -... $ ...-..- 3 ...- -
D -.. Q - -.- " .-..-. & .-... 4 ....-
E . R .-. ' .- - - -. / -..-. 5 .....
F ..-. S ... ! -.-.- - 6 -....
G - -. T - ? ..- -.. 7 - -...
H .... U ..- @ .- -.-. 8 - - -..
I .. V ...- - -....- 9 - - - -.
J .- - - W .- - ; -.-.-. 0 - - - - -
K -.- X -..- ( -.- -.
L .-.. Y -.- - ) -.- -.-
M - - Z - -.. = -...-

直接查表就好。

# split by space
dic = {'.-':'A','-...':'B','-.-.':'C','-..':'D','.':'E','..-.':'F','--.':'G','....':'H','..':'I','.---':'J','-.-':'K','.-..':'L','--':'M','-.':'N','---':'O','.--.':'P','--.-':'Q','.-.':'R','...':'S','-':'T','..-':'U','...-':'V','.--':'W','-..-':'X','-.--':'Y','--..':'Z','.-.-.-':'.','--..--':',','---...':':','.-..-.':'"','.----.':'\'','-.-.--':'!','..--..':'?','.--.-.':'@','-....-':'-','-.-.-.':';','.-.-.':'+','..--.-':'_','...-..-':'$','-..-.':'/','.----':'1','..---':'2','...--':'3','....-':'4','.....':'5','-....':'6','--...':'7','---..':'8','----.':'9','-----':'0'}

enc='.--- -... .-.. ..- .-- . .-- -. --..'.split(' ')
dec=""
for c in enc:
    dec+=dic[c]
print dec

一次性密码本(OTP)

例题:HCTF GAME 进击的 Crypto [1] - 神秘的加密系统

题目描述:http://119.29.138.57:23333/crypto/encode_system/(题目源地址,看运气还能不能打开)

我们随便输入,发现每次加密的结果都不一样,猜测加密的key不可能无限长,所以输入了非常长的一串‘1’,试出来key的长度为128bytes。然后观察加密后网页的源码,可以发现下面有flag_enc:

这里写图片描述

加密的方法是K xor M_input = C_input ,K xor Flag = Flag_enc。 而我们现在知道了M_input,C_input,Flag_enc。

所以Flag = K xor Flag_enc = (M_input xor C_input) xor Flag_enc。

先写个python脚本获取Flag_enc(此处吐槽一下为什么Flag_enc不base64或hex显示):

import urllib2
req = urllib2.Request( url = 'http://119.29.138.57:23333/crypto/encode_system/index.php', data = 'message=11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111')
response = urllib2.urlopen(req).read()
print response
print response[-131:-3].encode('hex')

从而得到了C_input和Flag_enc,python解密之:

c=[0x59,0x4f,0x72,0x5d,0x5c,0x07,0x72,0x6a,0x7e,0x50,0x07,0x67,0x49,0x44,0x15,0x6a,0x6f,0x7b,0x73,0x5e,0x77,0x18,0x50,0x53,0x59,0x08,0x6c,0x4f,0x40,0x4b,0x74,0x10,0x5d,0x5b,0x59,0x6f,0x15,0x05,0x01,0x62,0x1d,0x6d,0x7d,0x40,0x4c,0x62,0x7d,0x19,0x10,0x04,0x09,0x1b,0x68,0x5f,0x79,0x4d,0x19,0x7e,0x1c,0x4a,0x06,0x09,0x6e,0x55,0x51,0x08,0x12,0x1e,0x70,0x72,0x75,0x6d,0x72,0x70,0x40,0x6c,0x7d,0x04,0x42,0x5d,0x48,0x7f,0x07,0x1e,0x76,0x01,0x42,0x61,0x7a,0x67,0x43,0x00,0x74,0x7d,0x79,0x45,0x41,0x0d,0x55,0x58,0x7a,0x79,0x00,0x4a,0x07,0x52,0x76,0x45,0x04,0x15,0x45,0x44,0x15,0x4d,0x42,0x4b,0x42,0x42,0x5f,0x5d,0x69,0x63,0x5f,0x12,0x74,0x64,0x61,0x7b]

c_flag=list('3d11342d4c7230012d036e0c0523071a6a7e1e0b2f4d233d0166242f20286f1e47533903080459794965655529003909107b5f77154622146432744d66430e2e56715f5e043565682d004e6f2a760e3b4a1600476e4b18200f035d7a693d6417286f2d560720520f5018151d434141017b3f420a1b161c336c0d5f501a302a37'.decode('hex'))

b=[]
for i in range(128):
    c[i]=c[i]^ord('1')
    b.append(chr(c[i] ^ ord(c_flag[i])))
b=''.join(b)
print b
#result:UowA!DsZbbXZ}V#A44\didB_i_yQQR*?+9Q],0i*e9)$TSu!1Ng]L(jhL}Y6Q{QJ6H|qEv!4nA?2fC}W3X6h){kpDU/K,q,cXSI?Lhctf{Rive5t_C1pher_4_1s_ez}

得到flag:hctf{Rive5t_C1pher_4_1s_ez}