原创 CRC算法及CRC密码之探讨

 2009-7-1 00:34  2857 16 16 分类: MCU/ 嵌入式

原帖出处: <a href="http://bbs.pediy.com/showthread.php?t=92571">http://bbs.pediy.com/showthread.php?t=92571</a> <a href="">http://www.baigoogledu.com/search.asp?q=CRC+hotpower&num=20"]CRC</a>算法及CRC密码之探讨 CRC算法一般作为冗余校验之用，由于它的可逆性的不完整，导致了正规的CRC算法不能称之为CRC密码。 CRC之精华由初值、权、方向及位数组成，对其输入(明文)做CRC正运算得到输出的结果(密文)。 即：密文=CRC正运算(初值,权,方向,位数,明文); 反之，对其输出(密文)做CRC逆运算得到CRC的结果(明文)。 即：明文=CRC逆运算(初值,权,方向,位数,密文); 但要想实现CRC的可逆运算，必须满足： CRC右移时，CRC权的最高位为1. CRC左移时，CRC权的最低位为1. <a href="">http://www.baigoogledu.com/search.asp?q=%C8%BA%C4%A7%C2%D2%CE%E8+hotpower&num=20"][COLOR="Magenta"]CRC</a>种类繁多，经典的CRC皆为一表达式，及可得到一张CRC表。 例如： CRC8右移=X8+X5+X4+1 即二进制的100110001 权正确选择D8~D1 即10011000放弃最低位D0，即0x8c CRC8左移=X8+X2+X+1 即二进制的100000111 权正确选择D7~D0 即00000111放弃最高位D8，即0x07 这样处理后与标准CRC取权一致而且通俗一些。这样就可以将CRC算法可逆并升级为CRC密码。 虽然找到了CRC权与CRC算法可逆的关系： CRC右移时，CRC权的最高位为1. CRC左移时，CRC权的最低位为1. 但是传统的CRC算法是：本次的CRC初值是上次CRC运算的结果即密文。 这是CRC算法不能成为CRC密码的最大败笔所在!!! 因为在CRC运算过程中，权保持不变(查表方便),那么密文串中任意相邻的密文左端即为本次的初值。 那么，根据：明文=CRC逆运算(初值,权,方向,位数,密文)，立刻得出对应的明文。 即相邻的2个密文即可攻破1个明文。只要对CRC初值穷举后即可得到第1个明文。CRC密码即破解。 所以要实现真正的CRC密码，必须去掉CRC算法中本次初值是上次密文的约束，这样才能实现 CRC密码的可靠性。 再次张扬CRC之精华---初值、权、方向及位数. 如果在位数(或分组)一定时，若每次CRC运算都能保证初值、权、方向这3个CRC要素在变化且 不可逆，那么破译者只能是穷举一条路可走~~~ 对此我多年来研究了很多方法，简单举例： 我们可将某次CRC运算时的初值和权用上次的明文的扩散如<a href="">http://www.baigoogledu.com/search.asp?q=%C8%FD%BD%C7%C3%DC%C2%EB+hotpower&num=20"">[COLOR="blue</a>"]菜农的三角密码与上次的初值和权异或后得到 本次的初值和权。 由于为保证CRC密码的可逆而损失的1位密钥，我们可以用方向补偿。即每次CRC运算的方向(左移、右移) 都在变化。这样想推出某位的明文，在已知密文的条件下，必须知道上次的明文才能得出本次CRC的三要素。 即破解某位密文必须同时知道某位上次的明文和密钥才能破解某位的明文~~~ 同时知道了密文和明文还需要破解吗???这就是菜农想达到的目标~~~ 先谈到这里~~这几天朋友为我找密码专家教授一起探讨一番，所以先写点东西。 同时也欢迎这里的密码高手给以指点~~~ 下面给一链接，它实际是经过大量验证的CRC网上演算器，可以包含任意CRC算法。 <a href="">HotWC3">http://www.hotc51.com/HotPower_HotWC3.html"][COLOR="Red"]HotWC3</a>密码网上在线演算器 注意其中俺用“计算”和“还原”来代替“加密”和“解密”。意味CRC算法不能成为CRC密码. 关于HotWC3密码可参见:<a href="">http://blog.ednchina.com/hotpower/31641/category.aspx[/URL">http://blog.ednchina.com/hotpower/31641/category.aspx"]http://blog.ednchina.com/hotpower/31641/category.aspx[/URL</a>] [URL="<a href="http://www.hotc51.com/%22%5D">http://www.hotc51.com/"">[COLOR="Teal</a>"]菜农HotPower@126.com  2009.6.30 于<a href="">http://blog.ednchina.com/hotpower/"][COLOR="Red"][COLOR="DarkOrange</a>"]雁塔菜地   如何实现CRC算法的完全可逆 在上贴中，我们可以看到CRC算法的半可逆性，CRC右移时，CRC权的最高位为1. CRC左移时，CRC权的最低位为1. 即左移时，CRC权必须为奇数。同理右移是权也是取范围的一半。 我问过对CRC有所了解的朋友：“CRC运算是否可逆”。朋友回答：“可逆，有专著”。 那是因为标准的CRC表达式都为:CRCN=Xn+....Xm+...1.其中1即为X0. 而且大多的CRC算法都是左移的，且权都为奇数，如CRC16的1021. 如果将CRC算法变成CRC密码，则CRC三要素：初值、权及方向都不再有任何限制。 为满足CRC可逆，就必须限定权为取值范围的一半，这样CRC密钥(CRC三要素)中的权就降低了 加密强度1位。 为了不限制CRC权的取值范围，我们可以修正CRC算法： 正常的CRC运算中，有句异或权的语句，我们只需再加一句即可。 例如CRC8: 左移CRC8:       CRCVALUE ^= CRCPOLY;       CRCVALUE  |= 0x01;//强行满足CRC左移时，CRC权的最低位为1. 右移CRC8:       CRCVALUE ^= CRCPOLY;       CRCVALUE  |= 0x80;//强行满足CRC右移时，CRC权的最高位为1. 这样处理并未违反CRC算法，而且也未限定CRC权。从而实现了CRC算法的完全可逆。 大家知道算法和密码是有区别的。算法可以可逆和不可逆，但密码一定是可逆(加密和解密)的。   变异CRC运算使之成为真正的CRC密码 在前两贴中强调了CRC可逆后并不能成为真正的CRC密码，这主要归咎CRC算法中 本次CRC的初值是上次CRC运算的结果(密文)。 这使我们很容易从2个相邻的CRC密文导出本次的明文。 所以需要将CRC初值和CRC权都“动起来”。为了补偿CRC可逆对CRC权的限定，可以让方向也“动起来” 这样做后，CRC三要素：初值、权和方向就变成了CRC密钥了。 即知道CRC密钥和明文，才能得出与之对应的密文。 为了使每次CRC运算时，CRC三要素都在变化且和密文无任何关系，我们可以将上次的明文发散后得出本次 的CRC三要素，而且要保证发散是不可逆的。 这样解密者就不可能从密文串中推出其他CRC元素。这就牵扯到<a href="">http://www.baigoogledu.com/search.asp?hl=zh-CN&num=20&q=%C8%FD%BD%C7%C3%DC%C2%EB"">[COLOR="Red</a>"]三角密码的问题。   三角密码在CRC密码中的发散作用 谈到“三角密码”要追述到70年代初我小学快毕业时看了一本前苏联数学家有关直角三角形的论著， 很是头晕~~~ 等我上中学后用数学归纳的方法推出很菜而实用的“说法”： 在直角三角形中，已知一整数直角，求另一整数直角边和整数斜边。 即A^2+B^2=C^2  (^表示平方) 解： 若A为奇数时，A先平方后“砍半”即为B和C. 若A为偶数时，A先“砍半”后“手拉手”即为B和C. 例： 3   3^2=9  9/2=4和5     即3^2+4^2=5^2        4   4/2=2   2^2=4(3,5)  即4^2+3^2=5^2 以此类推，最后得出了<a href="">http://www.baigoogledu.com/search.asp?q=%C8%FD%BD%C7%C3%DC%C2%EB%B1%ED+HotPower&num=20"">“[COLOR="Red</a>"]三角密码表” 为何要用“三角密码表”发散呢？？？这源于密码学中的质数ucuo分解。 因为我的出发点在MCU,它的资源较小，分解质数肯定不行，故想到了小时候的“三角密码”。 前面已经反复论述了CRC运算不能成为CRC的因果关系，所以用三角密码来发散上次明文来充当 本次的初值和权是个不错的想法。 这样使解密难度增大，因为三角运算是平方级的运算，显然比一般的“与”“或”“异或”等难度要大。 因为它是特定条件下的三元二次方程。若无“直角三角形”“全为整数边”的特定条件，实为无解。 由于“三角密码表”为无重码进行了变换，且上次明文经三角变换后再与上次的初值和权异或，故它是不可逆的。 即无法从某次的密文中推出其他CRC元素，逼迫解密者只有穷举一条路。而且只能从第1个密文开始穷举。   <a href="">http://www.baigoogledu.com/search.asp?q=%D0%C7%C6%DA%CB%E3%B7%A8+%D0%C7%C6%DA%B9%AB%CA%BD+HotPower&num=20"">[COLOR="Red</a>"]星期密码对CRC密钥的保护作用 如上所述，CRC三要素实为CRC密钥。严格来讲其密钥长度为CRC位数的1倍。 由于CRC密码可分CRC8,CRC16...CRC64...CRC128,CRC256,则密钥长度16,8...128...256,512位. 故可以视为是一种分组密码。 破解CRC密码的关键是破解CRC三元素即CRC密钥，它的强度与分组的长度即CRC位数有关。 那么如何在MCU这样的小资源系统中得到高可靠的密码系统呢？？？如何降低分组？？？ 这样我想到了“星期密码”。那是我自己没事用计算机编程的思维推导出来的~~~竟然和122年的古人雷同。 由于“星期密码”是不可逆的，唯一的日期对应于唯一的星期，反之无解。 大家可能知道“<a href="">http://www.baigoogledu.com/search.asp?q=400%C4%EA%D2%BB%C2%D6%BB%D8+hotpower&num=20"">[COLOR="Red</a>"]星期四百年一轮回”，加上“天干地支”“六十年一甲子”，HotWC3就成为了组合密码。 它可以在小分组例CRC8密码上扩充密钥长度为日期密钥长度。甚至更长~~~ HotWC3密码经过星期及天干地支变换得到“天地密钥”，再经过三角变换收敛为CRC密钥，已满足CRC小分组密码。 最后“日期密钥”及“天地密钥”发散后对CRC密码的输入和输出作用最终得到HotWC3密码。这样也破坏了 穷举CRC密钥的企图。

工程师专属征文！分享知识经验，就能拿奖励～