精华内容
下载资源
问答
  • 试题 E: RSA 解密 【问题描述】 RSA 是一种经典的加密算法。它的基本加密过程如下。 首先生成两个质数 p, q,令 n = p · q,设 d 与 (p − 1) · (q − 1) 互质,则可 找到 e 使得 d · e 除 (p − 1) · (q − 1) ...

    Begin

    记录一下自己的学习过程啦~~

    上题目

    试题 E: RSA 解密

    【问题描述】
    RSA 是一种经典的加密算法。它的基本加密过程如下。
    首先生成两个质数 p, q,令 n = p · q,设 d 与 (p − 1) · (q − 1) 互质,则可
    找到 e 使得 d · e 除 (p − 1) · (q − 1) 的余数为 1。
    n, d, e 组成了私钥,n, d 组成了公钥。
    当使用公钥加密一个整数 X 时(小于 n),计算 C = Xd mod n,则 C 是加
    密后的密文。
    当收到密文 C 时,可使用私钥解开,计算公式为 X = Ce mod n。
    例如,当 p = 5, q = 11, d = 3 时,n = 55, e = 27。
    若加密数字 24,得 243 mod 55 = 19。
    解密数字 19,得 1927 mod 55 = 24。
    现在你知道公钥中 n = 1001733993063167141, d = 212353,同时你截获了
    别人发送的密文 C = 20190324,请问,原文是多少?

    思路过程

    1.已知n、d、c,求x( X =Ce mod n)
    2.要求x需求e
    3.结合已知条件,若要求e需求d与e的关系:(de-1)%[(p-1)(q-1)]==0
    4.若要求e、d间关系需求p、q
    5.p、q即为n的质因数

    代码

    数据较大时,这代码跑的着实的慢,还没想好怎么优化

    public class Main {
        public static void main(String[] args) {
            long[] a=new long[2];
            long n= 55L;
            long d= 3L;
            double c=24;
            double e,x;
            a=pq(n,d,a);
            long p=a[0],q=a[1];
            for(long i=1;i<=500000;i++){
                if((d*i-1)%((p-1)*(q-1))==0){
                    e=i;
                    System.out.println("e="+e);
                    break;
                }
            }
            x=Math.pow(c,d)%n;
            System.out.println("x="+x);
    		}
    
    	public static long[] pq(long n,long d,long[] a){
           long i;
           boolean j;
           for(i=2;i<=n;i++){
               if(!zhishu(i))
                   continue;
               if(n%i==0){
                   j=huzhi(d,(i-1)*(n/i-1));
                   if(zhishu(n/i)&&j)
                       break;
               }
           }
           a[0]=i;
           a[1]=n/i;
            System.out.println("p="+a[0]);
            System.out.println("q="+a[1]);
           return a;
        }
    
        public static boolean zhishu(long x){
            boolean y=true;
            for(int i=2;i<=Math.sqrt(x);i++){
                if(x!=2&&x%i==0){
                    y=false;
                    break;
                }
            }
            return y;
        }
    
        public static boolean huzhi(long a,long b){
            long t;
            while(b>0){
                t=a%b;
                a=b;
                b=t;
            }
            if(a==1)
                return true;
            else
                return false;
        }
        }
    
    

    总结

    1.互质

    定义:两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数,叫做互质数。
    判断:用大数除以小数,如果除得的余数与其中较小数互质,则原来两个数是互质数。

    2.求一个数的质因数

    
    	public int[] pq(int n,int[] a){
           int i;
           for(i=2;i<=n;i++){
               if(!zhishu(i))
                   continue;
               if(n%i==0){
                   if(zhishu(n/i))
                       break;
               }
           }
           a[0]=i;
           a[1]=n/i;
           return a;
        }
    
        public boolean zhishu(int x){
            boolean y=true;
            for(int i=2;i<=Math.sqrt(x);i++){
                if(x!=2&&x%i==0){
                    y=false;
                    break;
                }
            }
            return y;
        }
    

    3.判断两个数是否互质

        private static boolean get(int n, int m) {
    		int t=0;
    		while(m>0) {
    			t=n%m;
    			n=m;
    			m=t;
    		}
    		if(n==1)return true;
    		return false;
    	}
    
    展开全文
  • 第十届蓝桥杯 A组 RSA解密

    千次阅读 2019-03-24 17:58:55
    这次蓝桥杯对于acm学数学的太友好了 emmm 然而还是菜啊 我和填空最后一题死磕了一个小时 (太蠢了)没有Python写Java大数写到自闭 题目大意: n=p*q p,q为素数 d与(p-1)*(q-1)互素 (d*e)%((p-1)*(q-...

    这次蓝桥杯对于acm学数学的太友好了

    emmm 然而还是菜啊

    我和填空最后一题死磕了一个小时 (太蠢了)没有Python写Java大数写到自闭

     题目大意:

    n=p*q
    p,q为素数
    d与(p-1)*(q-1)互素
    (d*e)%((p-1)*(q-1))=1
    c=x^d%n
    x=c^e%n
    
    给定d,c,n
    求x
    

    素数筛可以求出p,q  用欧几里得验证是否满足互素条件,快速幂直接乘会爆longlong,所以要用快速乘+快速幂

    #Python 大法好
    p=891234941
    q=1123984201
    n=1001733993063167141
    c=20190324
    d=212353
    for i in range(1,500000):       #枚举因子   d*e%((p-1)*(q-1))=1    (((q-1)*(p-1))*yz+1) %d =0
        if(((p-1)*(q-1)*i+1)%d==0):
            e=((p-1)*(q-1)*i+1)//212353
            print(((p-1)*(q-1)*i+1)//d) 
            break
    def quick_mod(a,b,c):
        a=a%c
        ans=1
        while b!=0:
            if b&1:
                ans=(ans*a)%c
            b>>=1
            a=(a*a)%c
        return ans
    x=quick_mod(c,e,n)             #x=c^e%n   579706994112328949
    print(x)
    print(quick_mod(x,d,n))        #c=x^d%n

    为什么我的考场没有Python 啊啊啊o(╥﹏╥)o

    展开全文
  • RSA解密 我不会写,直接放弃~???? C++和Java版答案 完全二叉树的权值 把完全二叉树转化成数组就行了,节点对应数组下标,有这么的规律:设深度为deep,每一层最右边的为2^deep-1,所以再对应数组下标再-1就行了。...

    RSA解密

    在这里插入图片描述

    我不会写,直接放弃~🤣

    C++和Java版答案

    完全二叉树的权值

    在这里插入图片描述
    在这里插入图片描述

    把完全二叉树转化成数组就行了,节点对应数组下标,有这么的规律:设深度为deep,每一层最右边的为2^deep-1,所以再对应数组下标再-1就行了。

    public class Main {
    	public static void main(final String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n=sc.nextInt();
    		int[]nums=new int[n+1];
    		long maxSum=0;
    	    int minDeep=Integer.MAX_VALUE;
    		for(int i=1;i<=n;i++)nums[i]=sc.nextInt();
    		int deep=0;
    		for(int i=1;i<=n;i=i+(int)Math.pow(2, deep-1)) {
                long sum=0;
                //每一层可能不满,一定要加上j<=n,否则数组越界
                for(int j=i;j<i+(int)Math.pow(2, deep)&&j<=n;j++) {
                    sum+=nums[j];
                }
                if(sum>maxSum) {
                    minDeep=deep+1;
                    maxSum=sum;
                }
                deep++;
            }
    		System.out.println(minDeep);
    	}
    }
    
    展开全文
  • 自己通过这个题学到了很多知识 1.欧拉phi函数—详解 2.快速幂 3.代码来源 #include<bits/stdc++.h> #define ll long long using namespace std; ...inline ll ksc(ll x,ll y,ll mod) ... return (x*y-(ll)((long ...

    自己通过这个题学到了很多知识
    1.欧拉phi函数—详解
    2.快速幂
    3.代码来源(自己做了一点修改)

    #include<bits/stdc++.h>
    #define ll long long 
    using namespace std;
     
    inline ll ksc(ll x,ll y,ll mod)
    {
        return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod;     
    }
     
    ll fast_pow(ll x, ll k, ll p){
        ll ret=1;
        x%=p;
        while(k>0){
            if(k&1)ret= ksc(ret, x, p);       
            k>>=1;
            x= ksc(x, x, p);
        }
        return ret;
    }
    ll phi(ll n){
        ll ret= n;
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                ret= ret/i*(i-1);
                while(n%i==0) n/=i;
            }
        }
        if(n!=1){
            ret= ret/n*(n-1);
        }
        return ret;
    }
    ll get_p(ll n){
        for(ll i=2;i<=n;i++){
            if(n%i==0){
                return i;
            }
        }
    }
    int main(){
        ll n = 1001733993063167141;
        ll d = 212353;
        ll C = 20190324;
        ll p,q,e,k;
        printf("n=%lld\n",n);
        p=get_p(n);
        q=n/p;
        printf("p=%lld, q=%lld\n",p,q);
        k=(p-1)*(q-1);
        printf("k=(p-1)*(q-1)=%lld\n",k);
        printf("phi(k)=%lld\n",phi(k));
        e=fast_pow(d,phi(k)-1,k);
        printf("e=d^(phi(k)-1)=%lld (mod k)\n",e);
        printf("d*e=%lld (mod k)\n",ksc(d,e,k));
        ll X=fast_pow(C,e,n);
        printf("X=C^e (mod n)= %lld\n",X);
        return 0;
    }
    
    展开全文
  • 题目: 思路: 这题主要是数论知识 想明白了不难,但是要懂扩展欧几里得算法、快速幂、快速乘的知识 首先关于X有两条式子(mod 代表 % 意思) C=Xd mod n (第一条应该是求不出来的) X=Ce mod n 那我们肯定尽量要把e求...
  • 2019第十届蓝桥杯 省赛A组 RSA解密

    千次阅读 2019-04-25 15:24:44
    RSA算法介绍: 两个大素数p,q (保密的,选定的) n=p*q (n是公开的) Φ(n)=(p−1)(q−1) (即,欧拉函数:小于n且与n互素的数的个数) e满足gcd(Φ(n),e)=1; (1<e<Φ(n)) ,就是e与Φ(n)互质。 d*e≡1...
  • RSA解密蓝桥杯第十届省赛A组 扩展欧几里得算法(求逆元)+快速乘+快速幂,很综合的一道题。
  • 第十届蓝桥杯 省赛A组 E RSA 解密

    千次阅读 热门讨论 2019-03-24 17:42:51
    这个题应该是填空题中最难的一个了。 思路很简单,但是你需要一点...RSA是一种不可逆的加密方法,不可逆的原因是公钥特别大,对它分解质因子时间上会很长,普通计算机大概是 10年左右,量子计算机一星期就可以...
  • 思路:现在的要求是解密,所以按照公式,现在还差e,那么要求e就需要求p,q,根据公式(d*e)%(p-1)(q-1)=1可以知道p,q。 **注意,因为p,q是两个质数,所以他们的公因数只有1,所以n【n=p*q】只有这2个因子,没有...
  • 试题 E: RSA 解密 本题总分:15 分 问题描述 RSA是一种经典的加密算法。它的基本加密过程如下。 首先生成两个大质数p,q, 令n = p*q,设d与(p-1)*(q-1)互质,则可以找到e,使得d*e除以(p-1)*(q-1)的余数为1   n,d,e...

空空如也

空空如也

1 2 3
收藏数 51
精华内容 20
关键字:

蓝桥杯rsa解密