1. Home
  2. 学习打卡区
  3. RSA打卡

RSA打卡

  • 林

    rsa

    RSA算法简介

    选择两个大素数p和q，计算出模数N = p * q
    计算φ = (p−1) * (q−1) 即N的欧拉函数，然后选择一个e (1<e<φ)，且e和φ互质
    取e的模反数为d，计算方法: e * d ≡ 1 (mod φ)
    对明文m进行加密：c = pow(m, e, N)，得到的c即为密文
    对密文c进行解密，m = pow(c, d, N)，得到的m即为明文
    整理一下得到我们需要认识和记住的参数
    p 和 q ：大整数N的两个因子（factor）
    N：大整数N，我们称之为模数（modulus
    e 和 d：互为模反数的两个指数（exponent）
    c 和 m：分别是密文和明文，这里一般指的是一个十进制的数
    然后我们一般称
    （N，e）：公钥
    （N，d）：私钥

    CTF中的RSA题型

    CTF中的RSA题目一般是将flag进行加密，然后把密文（即c）和其他一些你解题需要的信息一起给你，你需要克服重重难关，去解密密文c，得到flag（即m），一般有下列题型

    公钥加密文
    这是CTF中最常见最基础的题型，出题人会给你一个公钥文件（通常是以.pem或.pub结尾的文件）和密文（通常叫做flag.enc之类的），你需要分析公钥，提取出（N，e），通过各种攻击手段恢复私钥，然后去解密密文得到flag。

    文本文档
    对于第一种题型，耿直点的出题人直接给你一个txt文本文档，里面直接写出了（N，e，c）所对应的十进制数值，然后你直接拿去用就行了。当然也不都是给出（N，e，c）的值，有时还会给出其他一些参数，这时就需要思考，这题具体考察的什么攻击方法

    pcap文件
    有时出题人会给你一个流量包，你需要用wireshark等工具分析，然后根据流量包的通信信息，分析题目考察的攻击方法，你可以提取出所有你解题需要用到的参数，然后进行解密

    本地脚本分析
    题目会给你一个脚本和一段密文，一般为python编写，你需要逆向文件流程，分析脚本的加密过程，写出对应的解密脚本进行解密

    远程脚本利用
    这种题型一般难度较大。题目会给你一个运行在远程服务器上的python脚本和服务器地址，你需要分析脚本存在的漏洞，确定攻击算法，然后编写脚本与服务器交互，得到flag

    RSA的常见攻击方法

    当模数N过小时
    RSA的非对称体制是建立在大整数分解难题上的，所以最基本的攻击方法就是当模数N过小时，我们可以写个脚本直接爆破他的因子，如
    N = 1211809
    for i in range(2, N):
    if N % i == 0:
    print i
    那么靠爆破来分解大整数N，我们可以分解多大的呢？
    2009年12月12日，编号为 RSA-768 （768bits,232 digits）数也被成功分解。—百度百科
    然而现在一般RSA在实际应用里都是2048位的，在CTF中出现的也不会太小，一般是不可能让你爆破分解的，都是要用到一些攻击算法的，下面我来介绍下这些算法

    分解大整数的一些算法
    如果说N小了容易被分解，那么N越大就越安全吗？不然，RSA密钥的安全不只和模数N有关，与它的指数：e和d也息息相关
    这里假设我们从题目获得了公钥（N，e）和待解密的密文c，由RSA的加解密过程，我们知道，如果要解密密文，我们要得到e的模反数d，而d是要我们去求解的。

    Wiener’s attack
    https://en.wikipedia.org/wiki/Wiener's_attack
    当 d < (1/3) N^(1/4)时，我们可以通过Wiener’s attack分解得到d

    费马分解
    当大整数N的两个因子p和q相近时，我们可以通过费马分解的办法很快分解大整数

    Small q
    当q较小时，即|p-q|较大时，我们可以直接爆破因子

    Boneh Durfee Method
    当d满足 d ≤ N^0.292 时，我们可以利用该方法分解N，理论上比wiener attack要强一些。

    yafu
    yafu使用最强大的现代算法去自动化的分解输入的整数。大多数的算法都实现了多线程，让yafu能充分利用多核处理器（算法包括 SNFS, GNFS, SIQS, 和 ECM）。

    factordb
    如果对一个大整数用一些特殊算法也分解不了的时候，我们可以在 http://factordb.com/ 中查询一下数据库，说不定就能找到其因子

    其他一些题型
    有些题会给你一些随机生成的大整数，一般来说是无法直接分解的，不过一般会给我们其他切入点

    Rabin算法
    当e等于2时

    小公钥指数攻击
    当e十分小时，比如e等于3时

    d泄露攻击
    如果我们知道一组过期的（N，e1，d1）和一组由新的e2组成的公钥及其加密的密文（N，e2，c），我们可以由（e1，d1）得到模数N的两个因子p和q，再去算e2的模反数d2，去解密密文

    共模攻击
    使用相同的模数 N 、不同的私钥，加密同一明文消息

    模不互素
    两个公钥的N不互素时

    Known High Bits Factor Attack
    我们知道模数N其中一个因子的高比特位时

    Stereotyped messages
    如果你知道明文中最重要的部分，您可以使用此方法找到消息的其余部分。

    Basic Broadcast Attack
    同一个加密指数e和不同且互素的模数N加密了同一个密文，并发送给了其他e个用户

    0
Log in to reply