文章目录
- 前言
- 一、Normal_RSA
- 二、使用步骤
- 1.下载附件
- 2.openssl
- 3.生成私钥
- 4.解密文件
- 总结
前言
题目描述：你和小鱼走啊走走啊走，走到下一个题目一看你又一愣，怎么还是一个数学题啊 小鱼又一笑，hhhh数学在密码学里面很重要的！现在知道吃亏了吧！你哼一声不服气，我知道数学 很重要了！但是工具也很重要的，你看我拿工具把他解出来！你打开电脑折腾了一会还真的把答案 做了出来，小鱼有些吃惊，向你投过来一个赞叹的目光
提示：以下是本篇文章正文内容，下面案例可供参考
一、Normal_RSA
题目链接：https://adworld.xctf.org.cn/task/answer?type=crypto&number=5&grade=0&id=5109&page=1
二、使用步骤
1.下载附件
flag.enc 看后缀enc，分析是一个通过openssl加密后生成的文件
pubkey.pem 应该是一个公钥信息文件
2.openssl
这里我使用kali系统，因为kali系统自带了openssl
先进入openssl
输入 rsa -pubin -text -modulus -in warmup -in pubkey.pem 查看信息
Exponent：指的是RSA中的e Modulus：指的是N，即pq相乘
代码语言：javascript复制Exponent：00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
be:30:dd
Modulus：65537先将16进制转为10进制，接着在线质因数分解 分解网址：http://www.factordb.com/
现在已得到的信息：
代码语言：javascript复制p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
e=655373.生成私钥
restool脚本代码
代码语言：javascript复制#!/usr/bin/env python3
import base64
import fractions
import argparse
import random
import sys
try:
import gmpy
except ImportError as e:
try:
import gmpy2 as gmpy
except ImportError:
raise e
if sys.version_info >= (3,5):
from math import gcd
else:
from fractions import gcd
from pyasn1.codec.der import encoder
from pyasn1.type.univ import Sequence, Integer
PEM_TEMPLATE = b'-----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 = 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.encodebytes(self.to_der())
def to_der(self):
"""
Return parameters as OpenSSL compatible DER encoded key
"""
seq = Sequence()
for idx, x in enumerate([0, self.n, self.e, self.d, self.p, self.q, self.dP, self.dQ, self.qInv]):
seq.setComponentByPosition(idx, 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)
def parts(s, l): return '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 = argparse.ArgumentParser()
parser.add_argument('-n', help='modulus. format : int or 0xhex', type=lambda x: int(x, 0))
parser.add_argument('-p', help='first prime number. format : int or 0xhex', type=lambda x: int(x, 0))
parser.add_argument('-q', help='second prime number. format : int or 0xhex', type=lambda x: int(x, 0))
parser.add_argument('-d', help='private exponent. format : int or 0xhex',
type=lambda x: int(x, 0))
parser.add_argument('-e', help='public exponent (default: %d). format : int or 0xhex' %
DEFAULT_EXP, default=DEFAULT_EXP, type=lambda x: int(x, 0))
parser.add_argument('-o', '--output', help='output filename')
parser.add_argument('-f', '--format', help='output format (DER, PEM) (default: PEM)',
choices=['DER', 'PEM'], default='PEM')
parser.add_argument('-v', '--verbose', help='also display CRT-RSA representation',
action='store_true', default=False)
args = parser.parse_args()
if args.p and args.q:
print('Using (p, q) to initialise RSA instancen')
rsa = RSA(p=args.p, q=args.q, e=args.e)
elif args.n and args.d:
print('Using (n, d) to initialise RSA instancen')
rsa = RSA(n=args.n, d=args.d, e=args.e)
else:
parser.print_help()
parser.error('Either (p, q) or (n, d) needs to be specified')
rsa.dump(args.verbose)
if args.format == 'PEM':
data = rsa.to_pem()
elif args.format == 'DER':
data = rsa.to_der()
if args.output:
print('Saving %s as %s' % (args.format, args.output))
fp = open(args.output, 'wb')
fp.write(data)
fp.close()
else:
sys.stdout.buffer.write(data)这里我使用了如下命令：
代码语言：javascript复制python3 -m pip install gmpy安装好需要的模块后输入命令：
代码语言：javascript复制python3 rsatool.py -f PEM -o private.pem -p 275127860351348928173285174381581152299 -q 319576316814478949870590164193048041239 -e 65537即可生成private.pem文件
4.解密文件
代码语言：javascript复制openssl rsautl -decrypt -in flag.enc -inkey private.pem
得到flag：PCTF{256b_i5_m3dium}
总结
- openssl
- gmpy
