分类

XOR 加密简介

作者: 阮一峰

日期: 2017年5月31日

本文介绍一种简单高效、非常安全的加密方法:XOR 加密。

一、 XOR 运算

逻辑运算之中,除了 ANDOR,还有一种 XOR 运算,中文称为"异或运算"。

它的定义是:两个值相同时,返回false,否则返回true。也就是说,XOR可以用来判断两个值是否不同。


true XOR true // false
false XOR false // false
true XOR false // true
true XOR false // true

JavaScript 语言的二进制运算,有一个专门的 XOR 运算符,写作^


1 ^ 1 // 0
0 ^ 0 // 0
1 ^ 0 // 1
0 ^ 1 // 1

上面代码中,如果两个二进制位相同,就返回0,表示false;否则返回1,表示true

二、 XOR 的应用

XOR 运算有一个很奇妙的特点:如果对一个值连续做两次 XOR,会返回这个值本身。


// 第一次 XOR
1010 ^ 1111 // 0101

// 第二次 XOR
0101 ^ 1111 // 1010

上面代码中,原始值是1010,再任意选择一个值(上例是1111),做两次 XOR,最后总是会得到原始值1010。这在数学上是很容易证明的。

三、加密应用

XOR 的这个特点,使得它可以用于信息的加密。


message XOR key // cipherText
cipherText XOR key // message

上面代码中,原始信息是message,密钥是key,第一次 XOR 会得到加密文本cipherText。对方拿到以后,再用key做一次 XOR 运算,就会还原得到message

四、完美保密性

二战期间,各国为了电报加密,对密码学进行了大量的研究和实践,其中就包括 XOR 加密。

战后,美国数学家香农(Claude Shannon)将他的研究成果公开发表,证明了只要满足两个条件,XOR 加密是无法破解的。

  • key的长度大于等于message
  • key必须是一次性的,且每次都要随机产生

理由很简单,如果每次的key都是随机的,那么产生的CipherText具有所有可能的值,而且是均匀分布,无法从CipherText看出message的任何特征。也就是说,它具有最大的"信息熵",因此完全不可能破解。这被称为 XOR 的"完美保密性"(perfect secrecy)。

满足上面两个条件的key,叫做 one-time pad(缩写为OTP),意思是"一次性密码本",因为以前这样的key都是印刷成密码本,每次使用的时候,必须从其中挑选key

五、实例:哈希加密

下面的例子使用 XOR,对用户的登陆密码进行加密。实际运行效果看这里

第一步,用户设置登陆密码的时候,算出这个密码的哈希,这里使用的是 MD5 算法,也可以采用其他哈希算法。


const message = md5(password);

第二步,生成一个随机的 key。


// 生成一个随机整数,范围是 [min, max]
function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

// 生成一个随机的十六进制的值,在 0 ~ f 之间 
function getHex() {
  let n = 0;
  for (let i = 4; i > 0; i--) {
    n = (getRandomInt(0, 1) << (i - 1)) + n;
  }
  return n.toString(16);
}

// 生成一个32位的十六进制值,用作一次性 Key
function getOTP() {
  const arr = [];
  for (let i = 0; i < 32; i++) {
    arr.push(getHex());
  }
  return arr.join('');
}

上面代码中,生成的key是32位的十六进制值,对应 MD5 产生的128位的二进制哈希。

第三步,进行 XOR 运算,求出加密后的message


function getXOR(message, key) {
  const arr = [];
  for (let i = 0; i < 32; i++) {
    const  m = parseInt(message.substr(i, 1), 16);
    const k = parseInt(key.substr(i, 1), 16);
    arr.push((m ^ k).toString(16));
  }
  return arr.join('');
}

使用这种方法保存用户的登陆密码,即使加密文本泄露,只要一次性的密钥(key)没有泄露,对方也无法破解。

(完)

留言(36条)

使用了RSS阅读器之后,阮老师的文章第一时间能看到了

请问,要是消息(message)和密匙(key)的位(bit)长度不一致,还可以进行异或操作吗?

对实例部分发表评论补充:由于单项散列函数的引入,使得无法通过一次性密钥反解出明文,实例中除了存储密文还要存储一次性密钥,开销是传统方式(只存散列值)的2倍。如果业务场景不是用于保存用户口令,而是用于加密传输数据,那么采用实例所述方法的性能将很差(要生成大于等于消息长度的一次性密钥),此法将变得不切实际,这也是一次性密码本最大的缺陷。

是为每一个密码都随机生成一个key还是大家用一个key?

最后那个哈希加密对储存密码并不合适。
一般储存密码会用加盬哈希,加盬的目的在于阻止彩虹表这类预先计算好哈希值的对应信息的攻击。
而用文中的方法,一旦黑客取得了保密信息和密钥,就能批量 XOR 算出原来的哈希值,再应用彩虹表攻击。
当然,文中假设密钥是对每个密码随机产生一组,分开储存且不会随密码外泄,但这不怎么现实……
其实反过来,先 XOR 再 md5 的话,也能达到文中的效果,而更能防止彩虹表攻击。
最后强调一点,学习密码学原理是很好的,但历史告诉我们不应自己发明加密方式,也不应自行实现加密标准,而要尽量使用公开且已被验证过的实现。

Information Theory 101: Claude Shannon was an American mathematician, not from UK.

stream cipher...

@-p*Log(p):

谢谢指出,已经改正。

能拿到密码密文自然就拿到key了 就算分开存 读一下代码就知道在哪了 sql能读文件 小黑路过 看大大的python入门的

还是先补充下可证明安全的知识吧

摘要(MD5)是用于验证。对摘要进行加密,还要额外存储key。解密的时候先要索引id取回key给client才能继续验证摘要。是多此一举。

“使用这种方法保存用户的登陆密码,即使加密文本泄露,只要一次性的密钥(key)没有泄露,对方也无法破解。”,既然黑客能拿到加密文本,那拿到加密key应该没什么难度吧?这和密码加盐好像没什么区别!

同意楼上观点。这个跟加盐后MD5的性质差不多。 不建议以这么简单的方式保存用户的登录密码,详细原因和替代方案见:

http://www.clarencep.com/2017/05/31/safe-way-to-store-password/

@sine:

位数少的补0呗

引用sine的发言:

请问,要是消息(message)和密匙(key)的位(bit)长度不一致,还可以进行异或操作吗?

看代码,字符串是一位一位对应加密的,如果key没有对应字符,会被截成'',任何数^''等于他自己,所以就是message多出的部分没有被加密

// 生成一个32位的十六进制值,用作一次性 Key
function getOTP() {
const arr = [];
for (let i = 0; i < 32; i++) {
arr.push(getHex());
}
return arr.join('');
}
=========================================
这不是生成一个32x4位的值吗?

请问随机生成16进制数为什么不能这样写呢?
function getHex() {
return getRandomInt(0,15).toString(16);
}

阮老师您好,经常看您的博客,我是一个前端菜鸟,想在您百忙之中问您点问题。我现在的JavaScript水平还在简单的特效,事件绑定等简单的层面,想继续学习比如模块化开发思想等,请问有什么好方法效率高一点学习吗?另外现在nodejs是必须要学习吗?现在用nodejs的还多吗?有发展前景吗?烦请阮老师在百忙之中看到评论回复一下,前端菜鸟不胜感激

有个大问题:如何保存一次性key?

刚学密码学?

每次加密随便找本书,摘取某些字作为一次性密码本,直接置换加密,照样安全的不行,还需要什么xor,脱离实际应用谈安全没有意义。

感觉没有实际使用意义,没想到合适的实际应用场景;
登录、注册都存在一个问题,key的管理,这个算法的key,说实话,及不易管理

---! 有不对的希望大家及时指正,thx!

我们以前在内网中传递参数的时候,会使用XOR进行简单的加密,没有想到还真的有这样的加密方式,还在实际中使用。

想到了一种植物

我们组客户端请求的时候会将所有参数组合后加椒盐(写死在客户端和服务端)再hash,然后再用md5加密,再发送到服务端,每(几)个接口用1个椒盐,服务端用对应的盐值来解密,得到参数。看上去和阮老师文中提到的"一次性密码本"有点像,但是生产环境中“一次性密码本”通常哪些方式实现呢?

第一个 例子里面顺序有错误
true XOR false // true
true XOR false // true

这个是一个对称加密吧,类似DES加密?

1.密钥的长度大于等于message,保证无信息泄露
2.密钥每次随机生成,一次一密

引用nnkken的发言:

最后那个哈希加密对储存密码并不合适。
一般储存密码会用加盬哈希,加盬的目的在于阻止彩虹表这类预先计算好哈希值的对应信息的攻击。
而用文中的方法,一旦黑客取得了保密信息和密钥,就能批量 XOR 算出原来的哈希值,再应用彩虹表攻击。
当然,文中假设密钥是对每个密码随机产生一组,分开储存且不会随密码外泄,但这不怎么现实……
其实反过来,先 XOR 再 md5 的话,也能达到文中的效果,而更能防止彩虹表攻击。
最后强调一点,学习密码学原理是很好的,但历史告诉我们不应自己发明加密方式,也不应自行实现加密标准,而要尽量使用公开且已被验证过的实现。

他举的例子应该是:XOR + OTP。

OTP每次生成的秘钥都是有时效的,服务端校验就可以了。服务端存储的值是密码的MD5值,当然这里存储的算法不太好。

两次XOR就能得到原始值。哈哈哈,大学的时候参加安全竞赛,就用这个方法解密了一个RC4加密。密钥不够长。

XOR加密原理是完美的,但应用上无法完美。就是无法获取OTP。
早期Wi-Fi的加密原理就是XOR,称为WEP加密,后来被证实是不安全的。再后来稍微加强了一些,变成了TKIP,即WEP2加密,但还是被证实是不安全的。其根本原因就是无法获取OTP。

单说这个例子,用户密码XOR加密完后在网络上传递,问题是,后台系统如何知道前端随机生成的key呢,是不是还再传输这个key,那么key又由谁来保护呢?

一次性密码本是可证实的最安全的加密方式,但是不能忽略一点,就是算法的可用性。
我们先了解一下加密的前提:密文需要在网络中传输,是可以自由获取的,但由于其保密性,所以,密文虽然公开可见,但其所包含的原始信息是安全的。

一次性密码本的密钥长度必须大于明文内容,否则明文超出密钥长度的内容无法加密。从存储角度来说,保存比明文内容还要长的密钥是不必要也不现实的。
假设一名黑客拥有某段消息的密文,但没有解密的密码,所以他不知道明文内容。一旦密文泄露,原文随之即被破解。所以一次性密码本的安全核心在于密钥本身的保密。
那么问题来了,我们拥有足够的能力永久保存比原文还要长的密钥不泄露,那么我们为什么还要加密呢?

所以,一次性密码本加密是理论上很强大的加密算法,但是真正的可用性几乎为零。拿来当游戏玩玩还是可以的

大家都在说key的保存问题,可以直接设置一个算法根据密码生成,为什么必须要保存。

引用爱冯果的发言:

大家都在说key的保存问题,可以直接设置一个算法根据密码生成,为什么必须要保存。

那么后面就需要讨论这个算法要怎么保存更安全了.

这个跟布尔函数有联系吗

引用Micooz Lee的发言:

对实例部分发表评论补充:由于单项散列函数的引入,使得无法通过一次性密钥反解出明文,实例中除了存储密文还要存储一次性密钥,开销是传统方式(只存散列值)的2倍。如果业务场景不是用于保存用户口令,而是用于加密传输数据,那么采用实例所述方法的性能将很差(要生成大于等于消息长度的一次性密钥),此法将变得不切实际,这也是一次性密码本最大的缺陷。



说得很对。 那么key长度不足,重复使用key之前位,那样key长度开销是不是就OK了?

我要发表看法

«-必填

«-必填,不公开

«-我信任你,不会填写广告链接