首页
社区
课程
招聘
[原创]三角密码探讨及揭秘
发表于: 2009-7-5 08:29 12109

[原创]三角密码探讨及揭秘

2009-7-5 08:29
12109
在直角三角形中,已知一整数直角,求另一整数直角边和整数斜边。

即A^2+B^2=C^2  (^表示乘方)


先引用我6年前一文中的话语:

整数直角三角形谜底——一种MCU加密解密算法

勾3股4弦5!每个人都明白。
对应的数学表达式:a^2+b^2=c^2.每个人都会!
但在a>=3且a,b,c都为整数的直角三角形问题中
已知a求b,c无穷解变成了数学归纳问题的唯一解。

例:                    解:
3^2 + 4^2= 5^2          9 +  16 = 25
4^2 + 3^2= 5^2         16 +   9 = 25
5^2 +12^2=13^2         25 + 144 = 169         
6^2 + 8^2=10^2         36 +  64 = 100
7^2 +24^2=25^2         49 + 576 = 625
8^2 +15^2=17^2         64 + 225 = 289
9^2 +40^2=41^2         81 +1600 =1681
.....................................................
255^2+32512^2=32513^2   65025+1057030144=1057059169
256^2+16383^2=16385^2   65536+ 268402689= 268468225
257^2+33024^2=33025^2   66049+1090584576=1090650625
258^2+16640^2=16642^2   66564+ 276889600= 276956164

数学归纳(加密过程):
当a为奇数时,b为a平方砍半取整,c比b大1。、
即 b="int"((a^2)/2). c="b"+1.

当a为偶数时,b为a砍半平方小1,c比b大2。
即 b=(a/2)^2-1. c="b"+2.

字节加密与解密问题:
    由于本算法从3开始,而字节值从0开始。故需加减3转换。

10进制表示
    原码A     密码B     密码C
      0(3)      4         5
      1(4)      3         5
      2(5)     12        13
      3(6)      8        10
      4(7)     24        25
      5(8)     15        17
      6(9)     40        41
      7(10)    24        26
。。。。。。。。。。。。。。。。。。。。。。。。。。
    252(255)  32512     32513
    253(256)  16383     16385
    254(257)  33024     33025
    255(258)  16640     16642

16进制表示
    原码A     密码B     密码C    (2字长)
     00        0004      0005
     01        0003      0005  (最小值为0003H,0005H)  
     02        000C      000D
     03        0008      000A
     04        0018      0019
     05        000F      0011
     06        0028      0029
     07        0018      001A
。。。。。。。。。。。。。。。。。。。。。。。。。。
     FC        7F00      7F01
     FD        3FFF      4001
     FE        8100      8101  (最大值为8100H,8101H)
     FF        4100      4102

合并密码B密码C为1个字长:
当a为奇数时有:  密码BC=(密码B/2)|0x8000
当a为偶数时有:  密码BC=密码B

16进制表示
    原码A     密码BC(1字长)
     00        8002 (变换)
     01        0003
     02        8006 (变换)
     03        0008
     04        800C (变换)
     05        000F
     06        8014 (变换)
     07        0018
。。。。。。。。。。。。。。。。。。。。。。。。。。
     FC        BF80 (变换)
     FD        3FFF
     FE        C080 (变换)
     FF        4100

解密过程:
当密码BC>0x8000时有:密码B=(密码BC*2)&0xffff 密码C=密码B+1
当密码BC<0x8000时有:密码B=密码BC             密码C=密码B+2

解密算法:
    原码A=(密码C^2-密码B^2)^(1/2)-3

若对密码B密码C进行2次CRC加密后,该算法将非常可靠。
以后,若有机会,我会道出“CRC的妙用”的。

当用于MCU时,昏天盖地的开方与乘方汇编产生的代码
一定会使解读者头昏眼花的!!!
因为解读者将搞不清原设计者在干些什麽活动???

HotPower在此声明:
    未经本人许可,本算法不得在任何地方发表。
否则,一切后果自负!
                2003。7。17


我对中学生讲时一般用(让他们骗他们的老师~~~):
若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,B,C中,C与B的差恒为1(A为奇数)或2(A为偶数)

当A为奇数时,有: A^2 = C^2 - (C - 1)^2 = 2*C - 1

当A为偶数时,有: A^2 = C^2 - (C - 2)^2 = 4*C - 4 = 4*(C-1)

例: 3^2 = 2 * 5 - 1 = 9
        4^2 = 4 * (5 - 1) = 16
        5^2 = 2 *13 - 1 = 25
        6^2 = 4*(10 - 1) = 36
        7^2 = 2 * 25 - 1 = 49

同理,因为C = B + 1(A为奇数)或C = B + 2(A为偶数)

当A为奇数时,有: A^2 = C^2 - (C - 1)^2 = 2*C - 1 = 2*(B + 1) - 1 = 2*B + 1

当A为偶数时,有: A^2 = C^2 - (C - 2)^2 = 4*C - 4 = 4*(C-1) = 4*(B+2-1)= 4* (B + 1)

例: 3^2 = 2 * 4 + 1 = 9
        4^2 = 4 * (3 + 1) = 16
        5^2 = 2 *12 + 1 = 25
        6^2 = 4*(8 + 1) = 36
        7^2 = 2 * 24 + 1 = 49

从表达式可以看出A和C及A和B之间“简单的关系”。这里C=B+1或C=B+2

从2*B+1,2*C-1或4*(B+1),4*(B+1)中我们可以发现:

求另一直角边B时用"+",求另一斜边C时用"-".

三角作为密码的初衷也起源于“椭圆曲线密码”和公开密钥算法中的大质数分解问题。

就前者可能是出于“图形”和圆方程A^2 + B^2 = 1的“相似”

后者是2个质数是不同的,而三角密码涉及的“乘方”是2个相同的“质数”~~~

就图形而言,圆是椭圆的一个特例,三角是圆上的三点~~~他们都是亲戚~~~

对质数而言,它不过是个简单的三元一次方程,而三角却是一个三元二次方程。

大质数的命题:n=pq,2个大质数p和q的积为n.命题是n“很难分解出”p和q.

试想一个“大整数直角边”要想得到(分解)出“一个大整数直角边和斜边”

也是难度很大~~~不过“三角陷门”把问题简化为了乘方和开方问题~~~

由于C=B+1,2,故三元三次方程实际简化为X^2=Y;(其中Y=2*Z+-1或Y=4*(Z+-1))

或y=x*x. 这和n=p*q很相似吧~~~当p=q时它们就是一家了~~~

所以用三角做密码是柔和了椭圆和大质数的共同特点。

先到这里,菜农随意惯了,想到哪里写到哪里,很是抱歉~~~

能搞明白俺的思路,脑浆必须属于“发散型的散列函数”~~~

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

收藏
免费 0
支持
分享
最新回复 (17)
雪    币: 1450
活跃值: (35)
能力值: (RANK:680 )
在线值:
发帖
回帖
粉丝
2
当密码BC>0x8000时有:密码B=(密码BC*2)&0xffff

这里是否应该是这样:
密码B=(密码BC&0xefff)*2 .
2009-7-5 09:17
0
雪    币: 1450
活跃值: (35)
能力值: (RANK:680 )
在线值:
发帖
回帖
粉丝
3
感谢菜农大师分享。
此算法的精妙之处在于就在于虽然加解密涉及到很多乘方开放运算但算法却来源于大家最熟悉的勾股定理。

但是, 逆向解密者在不知道算法的原理(也即本贴所谈三角密码)情况下,也完全可以绕过正规解密算法“A=(密码C^2-密码B^2)^(1/2)-3”而直接解密的。 因为由原码A到密码BC实际上还是可逆的。

不过大师的思路很巧妙, 期待大师更多的精品。
2009-7-5 09:25
0
雪    币: 129
活跃值: (1095)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
三角密码的编码问题

既然三角及勾股问题可以划归为密码,那么密码也有个编解码的问题。

菜农的原意是在小资源的系统中实现三角密码的加密和解密,故想抛开乘方和开方的算法。

当初是为加大CRC密码的难度并保护CRC密钥而限定三角密码的A码为1字节内。

因为:

3^2 + 4^2 = 5^2
4^2 + 3^2 = 5^2
............................
258^2 + 16640^2 = 16642^2

故一字节的A码对应于2字节的B码或C码。这样就实现了1字节扩散为2字节。

做为密码肯定需要编码的可逆和迅速扩散且非线性,三角编码完全满足其需要。

A与B或A与C的关系简化后:

A^2=Y;(其中Y=2*B+1或2*C-1或Y=4*(B+1)或Y=4*(C-1))

由于B码没“重码”,C码有5(3,4,5或4,3,5),故只需B码即可

合并密码B密码C为1个字长的编码(BC码):
当a为奇数时有:  密码BC=(密码B/2)|0x8000
当a为偶数时有:  密码BC=密码B

解密过程:
当密码BC>0x8000时有:密码B=(密码BC*2)&0xffff 密码C=密码B+1
当密码BC<0x8000时有:密码B=密码BC             密码C=密码B+2

实际编解码在三角密码源程序中采用:

function password(passa)
{
var passbc;
  passbc = eval(passa) + 3;
  if(passbc & 1){//数据变换,将4字节压缩为2字节密码BC
    passbc = Math.pow(passbc,2);
    passbc = (passbc >> 2) | 0x8000;
  }
  else{
    passbc = (passbc >> 1);
    passbc = Math.pow(passbc,2) - 1;
  }
  return passbc;//返回压缩密码BC
}

function dispassword(passbc)
{
var passba, passb, passc;
  if(passbc >= 0x8000){//数据变换还原
    passb = (passbc & 0x7fff) * 2;
    passc = passb + 1;
  }
  else{
    passb = passbc;
    passc = passb + 2;
  }
  passa = Math.pow(passc, 2) - Math.pow(passb, 2);//计算直角边a
  passa = Math.sqrt(passa) - 3;//转换为原码A
  return passa;//返回原码A
}

编码容易解码难,编码可以用1个字节查询离散的2个字节编码表,想要编制解码表就需要更大的空间。

采用编码主要是想抛开开方和乘方。

注意:

合并密码B密码C为1个字长:
当a为奇数时有: 密码BC=(密码B/2)|0x8000
当a为偶数时有: 密码BC=密码B


中的密码BC=(密码B/2)|0x8000主要是为解码可逆埋下的伏笔,否则解码也只能做表格了。
2009-7-5 11:44
0
雪    币: 1450
活跃值: (35)
能力值: (RANK:680 )
在线值:
发帖
回帖
粉丝
5
LZ能否认真的看看我在二楼的回帖?

如果是笔误的话, 还请LZ改正. 以免给大家阅读帖子带来不便. 谢谢.
2009-7-5 12:57
0
雪    币: 2067
活跃值: (82)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
6
制造孤独 ?
2009-7-5 14:19
0
雪    币: 129
活跃值: (1095)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
看花眼了,密码B=(密码BC&0xefff)*2????

应该是密码B=(密码BC&0x7fff)*2吧
2009-7-5 15:24
0
雪    币: 129
活跃值: (1095)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
孤独和独孤可谓天地之别,俺是菜鸟,应该属于前者。
2009-7-5 15:49
0
雪    币: 129
活跃值: (1095)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
9
三角密码的可逆和变换问题

创立三角密码的初衷是为了保护CRC密钥,即1字节的A码发散为BC码。

再将2字节的BC码拆成1字节的BCH做CRC密钥中的初值,另1字节BCL做CRC密钥中权

我们可以从三角密码表看到只有一个“弱密钥”

它就是A码=0xff时,BC码为0x4100,其中低8位的0x00即权就是一个"弱密钥"。

由于CRC密码采用了可逆处理程序,故此“弱密钥”也同时被“化解”。

故三角密码进行三角变换后的编码非常适合做CRC的密钥即HotWC3密码系统中的子密钥。

可能有人会提出疑问:既然三角密码可逆,那么CRC密钥也就可逆,这样CRC密码就可从明文流中有可能推导出密钥来。

不然。因为CRC密码混合三角密码主要是扩散,故不需要可逆而需要散列。

A码可以导出BC码,BC码可反推出A码。

但是将A XOR  BCH 和 A XOR BCL后就变成散列的CRC密钥了。何况再有明文参与呢???

三角形的研究领域很广,总有人感觉是个“很菜”的问题,那他应该先研究一下三角形的“五心”
2009-7-5 16:25
0
雪    币: 1450
活跃值: (35)
能力值: (RANK:680 )
在线值:
发帖
回帖
粉丝
10
不好意思, 真的看花眼了.
希望hotPower接下来能给大家分享更多的知识.
2009-7-5 22:16
0
雪    币: 155
活跃值: (29)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
11
无字天书。。。。。。。
2009-7-6 12:21
0
雪    币: 129
活跃值: (1095)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
12
哈哈~~~一片白纸。
2009-7-7 15:43
0
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
13
從 1 樓到現在,我沒看見有 BCHBCL 出現過,請問是否方便講解一下 BCH 及 BCL是什麼? 還是筆誤?
謝謝。
2009-7-7 21:47
0
雪    币: 129
活跃值: (1095)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
14
BCH是BC的高8位,BCL是BC的低8位。

它主要在HotWC3密码体系中起生成CRC子密钥(BCH做CRC初值,BCL做CRC权值)的作用。

为了破坏三角密码的可逆关系,实际采用:

CRC初值 ^= A ^ BCH;(0为弱密钥,可以用明文1或2^(N-1)攻击权,但HotWC3采用一次一密攻击无果)  
CRC权   ^= A ^ BCL;(0为弱密钥)

其中A为三角变换前的输入,BC(CBH,BCL)为变化后的输出。
    CRC子密钥(初值,权,方向)。
    方向 = 初值 > 权;  (真为左移,假为右移)

所以要想攻击CRC子密钥是有难度的。
2009-7-8 21:46
0
雪    币: 164
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
15
lz思路确实比较发散

偶水平实在太凹,没看出来lz的三角密码和a->b这种密码表有什么本质的区别,或者说有什么更高明之处
2009-7-11 17:34
0
雪    币: 129
活跃值: (1095)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
16
回复blackboy:

你可能看了我最近的几个帖子,如“碰撞”,S盒等。

由于我是要打造一个新的流加密体系,可能有人觉得好笑,但实话说现在军事、外交和通讯
都是广泛采用流加密体系而非分组加密体系,原因“不详”~~~

分组和流即序列加密体系各有所长,关键都是对密钥的混淆及扩展。以达到保护密钥免受攻击的目的。

HotWC3选择三角密码做密钥的保护模块主要是它可以用1个字节发散为2个字节来作为CRC密码的初值和权。

其他算法可以吗???当然什么都可以。

三角密码刚好符合单字节发散为双字节后不溢出。而且它类同“椭圆曲线密码”,我在有些帖子中谈过相应话题。

它同时也有公开密码体系的影子,即素数问题,不过它是2个相同的整数~~

再“三角密码表”实际是专为CRC密码打造的,无任何“高明之处”可言。
2009-7-11 18:51
0
雪    币: 129
活跃值: (1095)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
17
但是, 逆向解密者在不知道算法的原理(也即本贴所谈三角密码)情况下,也完全可以绕过正规解密算法“A=(密码C^2-密码B^2)^(1/2)-3”而直接解密的。 因为由原码A到密码BC实际上还是可逆的。


理解有问题,三角密码的BC码实际不包含C码!!!

因为C与B的差值固定(1或2),故没有C后A与B的关系实际是无法形容的。
只是在编码中附加了一个“奇偶标志”。用它隐含C与B的差值。

这样对BC码(变异后取出C的B码)解码后方可从“奇偶标志”中解出C来。
实际应用根本不考虑其存在。
2009-7-11 20:34
0
雪    币: 164
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
18
谢谢HotPower的耐心回复

之前理解的有所偏差
我充充电先~
2009-7-12 11:14
0
游客
登录 | 注册 方可回帖
返回
//