一、赛题名称:RSA 加密体制破译 二、赛题描述 1.1 问题描述 RSA 密码算法是使用最为广泛的公钥密码体制。该体制简单且易 于实现，只需要选择 5 个参数即可(两个素数和、模数 = 、加 密指数和解密指数)。设为待加密消息，RSA 体制破译相当于已 知 mod ，能否还原的数论问题。目前模数规模为 1024 比特的 RSA 算法一般情况下是安全的，但是如果参数选取不当，同样存在被 破译的可能。 有人制作了一个 RSA 加解密软件(采用的 RSA 体制的参数特点描 述见密码背景部分)。已知该软件发送某个明文的所有参数和加密过 程的全部数据(加密案例文件详见附件 3-1)。Alice 使用该软件发送 了一个通关密语，且所有加密数据已经被截获，请问能否仅从加密数 据恢复该通关密语及 RSA 体制参数?如能请给出原文和参数，如不能 请给出已恢复部分并说明剩余部分不能恢复的理由? 1.2 实例破解 在本次竞赛问题中，我们选取了一个具体加密实例供大家破解， 整个算法与加密过程描述如下，截获的加密数据见附件 3-2。 1/4 首届(2016)全国高校密码数学挑战赛之赛题三
- RSA 密码算法描述如下，包含体制参数选取和加解密过程。 1)RSA 体制参数选取 Step1. 每个使用者，任意选择两个大素数和，并求出其乘积 = 。 Step2. 令() = ( − 1)( − 1),选择整数，使得GCD(, ()) = 1， 并求出模()的逆元，即 ≡ 1 mod (). Step3. 将数对(,)公布为公钥，保存为私钥。 2)加解密过程 Bob 欲传递明文给 Alice，则 Bob 首先由公开途径找出 Alice 的公 钥(, )，Bob 计算加密的信息为: ≡ mod 。 Bob 将密文传送给 Alice。随后 Alice 利用自己的私钥解密: ≡() ≡ ≡mod.
- Alice 使用的 RSA 密码体制，有以下事项需要说明:
- 模数 = 规模为 1024 比特，其中，为素数;
- 素数由某一随机数发生器生成;
- 素数可以随机选择，也可以由 2)中的随机数发生器产生;
- 可以对文本加密，每次加密最多 8 个明文字符;
- 明文超过 8 个字符时，对明文分片，每个分片不超过 8 个字符;
- 分片明文填充为 512 比特消息后再进行加密，填充规则为高位添加 64 比特标志位，随后加上 32 比特通信序号，再添加若干 个 0，最后 64 比特为明文分片字符对应的 ASCII 码(注:填充 方式参见加密案例，但注意每次通信的标志位可能变化); 2/4 首届(2016)全国高校密码数学挑战赛之赛题三
- 分片加密后发送一个加密帧数据，帧数据文件名称为 FrameXX， 其中 XX 表示接收序号，该序号不一定等于通信序号;
- 帧数据的数据格式如下，其中数据都是 16 进制表示，结构如下 1024bit 模数 N | 1024bit 加密指数 e | 1024bit 密文 me mod N。 9) 由于 Alice 初次使用该软件，可能会重复发送某一明文分片。 1.3 成绩评判 通过数论方法获得的原始明文及 RSA 参数数量，数量多者获胜。 三、国内外研究进展与现状 RSA 的安全性是基于大整数素因子分解的困难性，而大整数因子 分解问题是数学上的著名难题。数域筛法是目前 RSA 攻击的首选算法。 在 1999 年，一台 Cray 超级电脑用了 5 个月时间分解了 512 比特长的 密钥。在 512 比特 RSA 算法破解 10 年之后,即 2009 年 12 月 9 日，768 比特 RSA 算法即 232 数位数字的 RSA-768 被分解。分解一个 768 比特 RSA 密钥所需时间是 512 位的数千倍，而 1024 比特所需时间则是 768 比特的一千多倍，因此在短时间内 1024 比特仍然是安全的。除此之 外，目前对于 RSA 算法的攻击主要有以下方式:选择密文攻击、公共 模数攻击、低加密密指数攻击、低解密指数攻击、定时攻击等等，详 细的 RSA 安全分析参见有关文献。