美文网首页
一个简单的RSA选择密文攻击

一个简单的RSA选择密文攻击

作者: 无令便逐风 | 来源:发表于2017-10-27 20:54 被阅读0次

简述题意: 已知RSA加密的公钥,即(N, e),一个对应的解密函数。这个解密函数可以解密除了C*之外的密文,返回明文。
目的: 求C*对应的明文。

解密头文件

#ifndef DEC_H_INCLUDED
#define DEC_H_INCLUDED
char* dec(const char *c_inp);
#endif // DEC_H_INCLUDED

解密思路:
[下面的计算都是在 mod N 的前提下进行的]
取某个常数u, 使得C" = ue
假设C*对应的明文是M*, 那么根据RSA的加密原理有 (M*)e = C*
那么有 C* × ue = (M*)e × ue = (M* × u)e, 把(M* × u)e 看成是一段可被解密程序接受的密文feasible_cipher 进行解密
解密结果应该是M* × u, 此时解密结果 / u 即可得M*
值得留意的是构造的密文(M* × u)e 无法确定(M* × u) 是否大于N(违背了要求)。对于明文长度大于N的数据,会发生回绕,失去原有可逆属性。
如果如下面我的例子简单取u = 2,那么可以用简单的方法通过输出的2×M*来判断(M* × u) 是否大于N

#include<iostream>
#include<gmp.h>
#include<gmpxx.h>
#include"dec.h"
using namespace std;

/*bn : BigNumber*/
typedef mpz_class bn;

const char* N_str = "10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531469002933770824382865926730400902798743137187335810705309884635534159797732259520594337385186897629868362414475309001507719259272508669419676508606630823351242964205044695669333236417591";
const char* e_str = "10335071977839588495324343307012721241868030345867699233451500809021555989403028103743221782417440900848403102247012012875905268518785845678756696925714007988778268752026049276281025329038071087021446834856566687537729918372863729292015978809506607411711073716898691660211835403800810547133032654209857";
const char *c_star_s = "775789568255447714013247918834475198679653917741675336925599335265205597974556878796619688391490153400553690715156825186410083467239441867930362368759072824742512821423959166270736914130604102452801162684877374802075310241079026986641176079329871431448404341153307957496668749957011118721172866996397";
const char *m_text_s = "2";


/**
 * 快速幂取模,输入a, b, c
 * 返回: a^b mod c
 */
bn F_exp(bn a, bn b, bn c) {
    bn ans = 1;
    a %= c;
    while (b != 0) {
        if (b % 2 != 0) ans = (ans * a) % c;
        a = (a * a) % c;
        b >>= 1;
    }
    return ans;
}
/**
 * 快速乘取模,输入a, b, c
 * 返回: a*b mod c
 */
bn F_mul(bn a, bn b, bn c) {
    bn ans = 0;
    a %= c;
    while (b != 0) {
        if (b % 2 != 0) ans = (ans + a) % c;
        a = (a + a) % c;
        b >>= 1;
    }
    return ans;
}

int main() {
    bn N(N_str, 10);            // 模数N
    bn e(e_str, 10);            // 公钥组成成分 e
    bn c_star(c_star_s, 10);    // 密文c*
    bn m_text(m_text_s, 10);    // 待解m*

    bn cpie = F_exp(2, e, N);   // c"  即2^e
    /*bn feasible_cipher = ((c_star % N) * (cpie % N)) % N*/
    bn feasible_cipher = F_mul(c_star, cpie, N);

    char *m_times2 = dec(feasible_cipher.get_str().data());
    bn m2(m_times2, 10);
    bn res = m2 / 2;

    /**
     * n是两个大素数pq之积,且两者都不取2,故n必为奇数(因子只有1, n, p, q)
     * 因m < n, 故2m < 2n, 2m为偶数,假设2m>n,则2m%n=2m-n, 偶数-奇数=奇数
     * 而此题结果2m = 202为偶数,且不为0,所以2m<n 
     */
    cout<<"---- RESULT ----\n";
    cout<<(m2 % 2 != 0 ?  "m wrong" : res.get_str()) <<"\n";
    return 0;
}

编译链接命令
g++ -g -std=c++11 -Wall dec_rsa.cpp dec.o -o Result -lgmp -lgmpxx
解得原文 M* = 101

相关文章

  • 一个简单的RSA选择密文攻击

    简述题意: 已知RSA加密的公钥,即(N, e),一个对应的解密函数。这个解密函数可以解密除了C*之外的密文,返回...

  • 用大数实现RSA选择密文攻击

    选择密文攻击(CCA):攻击者选择一些密文,并获得相应的明文,这些明文是利用目标对象的私钥解密获得的。利用RSA的...

  • Android-RSA算法加密解密

    安卓中利用RSA算法加密和解密 整个流程大致为:生成密钥对->获取公私钥->对明(密)文加(解)密。 RSA算法每...

  • 威胁模型(Threat Model)

    1.唯密文攻击:最基本的攻击模型。敌手仅仅观察得到密文,并试图得到明文。 2.已知明文攻击:敌手知道用某密钥加密的...

  • RSA-Pycrypto

    RSA 密码算法与签名RSA是一种公钥密码算法,RSA的密文是对代码明文的数字的 E 次方求mod N 的结果。也...

  • IOS客户端实现RSA加密

    生成密文的长度和明文长度无关,但明文长度不能超过密钥长度不管明文长度是多少,RSA 生成的密文长度总是固定的。但是...

  • 2018-07-20

    密码相关 之前一直混淆加密解密(rsa)何散列碰撞(sha)之间的区别,现在明白了,rsa做的是明文和密文之间的转...

  • RSA模数攻击

    当使用公共的模数n,不同的私钥e1, e2对同一密文进行加密时,如果能截获密文c1, c2那么可能可以直接解密。 ...

  • Linux 免密登陆

    步骤一: 生成本地密匙 如果本地没有密匙, 首先需要创建一个自己的密匙,使用ssh-keygen -t rsa,一...

  • RSA、Diffie-Hellman和中间人攻击

    背景 网络上常常有对RSA、DH算法,以及中间人攻击的讨论。一种说法是“RSA密钥协商(交换)不会受到中间人攻击”...

网友评论

      本文标题:一个简单的RSA选择密文攻击

      本文链接:https://www.haomeiwen.com/subject/igpdpxtx.html