「密码学」-Merkle-Hellman

2019-09-26 本文已影响0人雨落八千里

$Merkle-Hellman$ 背包密码体制

加密：
选择任何一个超递增集 $\{s_1,s_2,...,s_n\}$ 。陷门有任意大于 $\sum_is_i$ 的素数 $p$ 和任意小于 $p$ 的整数 $a$ 组成，这两个数和集合 $\{s_1,s_2,...,s_n\}$ 都是保密的。公开的整数集是 $\{t_1,t_2,...,t_n\}$ ,其中 $t_i=a_i*s_i(mod\ \ \ p)$ 。二进制明文 $(b_1,b_2,...,b_n)$ 的加密操作为 $y=\sum_ib_it_i$ 。整数 $y$ 是密文。

解密：
找到 $a^{-1}(mod\ \ p)$ 。因为 $p$ 是质数， $a^{-1}(mod\ \ p)$ 一定存在。计算 $a^{-1}y (mod\ \ p)$ 。得到 $a^{-1}y (mod\ \ p)$ 这使得
$a^{-1}y=a^{-1}\sum_ib_it_i(mod\ \ p)=\sum_ib_i(a^{-1}as_i)(mod\ \ p)=\sum_ib_is_i$
因为集合 $\{s_1,s_2,...,s_n\}$ 是超递增集，所以很容易定位明文位

超递增集：每一个整数都大于它前面整数之和
陷门：超递增集必须被隐藏在陷门后
$a^{-1}(mod\ \ p)$ ： $a^{-1}$ 是a在模 $p$ 的情况下的逆元

习题

给定一个超递增集 $\{3,5,11,20,41,81,167,339\}$ 和素数 $701$ 以及一个整数 $a=223$ ，构造一个 $Merkle-Hellman$ 加密集 $\{t_i\}$ 。对二进制消息 $(10011101)$ 进行加密；并对密文进行解密。

依题意可知:
$s=\{3,5,11,20,41,81,167,339\}$
$p=701,a=223$
$b=(10011101)$

加密过程：
根据 $t_i=a_i*s_i(mod\ \ \ p)$ ，可以得到 $t=\{669,414,350,254,30,538,88,590\}$
密文 $y=\sum_ib_it_i$ 。可以得到 $y=2081$

解密过程：
通过扩展欧几里得可以得到 $a$ 在模 $p$ 的情况下的逆元 $a^{-1}=679$
所以 $\sum_ib_is_i=a^{-1}y=484$
$484=s_1+s_4+s_5+s_6+s_8$
$b=(10011101)$

扩展欧几里得：

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;
void exgcd(ll a,ll b,ll &gcd,ll &x,ll &y)
{
   if(b==0)
   {
       gcd=a;
       x=1;
       y=0;
   }
   else
   {
       exgcd(b,a%b,gcd,y,x);
       y-=x*(a/b);
   }
}
ll inv(ll a,ll b)
{
   ll gcd,x,y;
   exgcd(a,b,gcd,x,y);
   return gcd==1?(x%b+b)%b:-1;
}
int main( )
{
   ll a,b;
   while(~scanf("%lld%lld",&a,&b))//a是被模数,b是模数,-->a%b
   {
       printf("%lld\n",inv(a,b));
   }
   return 0;
}

「密码学」-Merkle-Hellman

$Merkle-Hellman$ 背包密码体制

习题

猜你喜欢

热点阅读