-
-
[原创]流密码内嵌魔方阵于随机存档之研究-- Magic Square 之神奇篇
-
2009-5-25 06:22
-
然后接【原创】流密码内嵌魔方阵于随机存档之研究-- Magic Square 篇 继续讨论。
我在前几帖有介绍到 magic square 的应用，今天我更深入介绍 magic square 一些特性。
Magic square 本身是一个 matrix，如果把它应用在 encryption/decryption，算是 block cipher 的一种，我想它被归类在 block cipher 应该不会有人有意见。
截至目前为止，我们所谈论的 magic square 都是 normal type，什么是 normal type？简单的来讲，就是有多少格子，就有多少数字，而且每一个 column ，每一个 row ，及每一个 cross 的总和都相等。
它的万用公式为
譬如以 3 by 3 为例子，
，所以 3 by 3 的 magic square 的每一 line 的总和是 15。
当 sender encrypt 一个东西之后，他最少要传 ciphertext 及 key 这两样东西给 receiver，receiver 根据 key (or password) 来把 ciphertext decrypt 成 plaintext。这是最基本的情况。
如果 encrypt key 及 decrypt key 是一样的，那通常是 symmetric cryptosystem，如果不一样，通常是 asymmetric cryptosystem。
如果要让 receiver 对 sender 做 authenticated 的动作时，sender 至少还要 plaintext, key 及 ciphertext 三种给对方，receiver 可以把 ciphertext decrypt 后，跟原来的 plaintext 比对看看是否一致。
symmetric cryptosystem与asymmetric cryptosystem 各有它的特性，但却无法解决目前的一个问题，什么问题？
Send 最少要传 plaintext 及 key 给 receiver。
有没有什么方式是可以只传 ciphertext 而不用传 key 就可以达到前面所讲的那样？
目前所知的 cryptosystem 技术是办不到的。连 quantum cryptosystem 也不例外。
现在再回过头来讲 magic square。
以 3 by 3 magic square 来看，两个对角的和分别是 (8+2)=10，(6+4)=10。
因3 *3 =9，但 10 比9 大1。
再来看 4 by 4 magic square。
两个对角的和分别是 (16+1)=17，(13+4)=17。因 4 * 4 =16，但 17 比 16 大1。
再来看 5 by 5 magic square。
两个对角的和分别是 (17+9)=26，(15+11)=26。因 5 * 5 =26，但 26 比 25 大1。
接着看 6 by 6 magic square。
两个对角的和分别是 (32+7)=39，(21+14)=35。这两个对角合不一样，比较特别一点。
先计算 (39+35)=74， 74/2=37，因 6 * 6 =36，但 37 比 36 大1。
接着看 7 by 7 magic square。
两个对角的和分别是 (30+20)=50，(28+22)=50。因 7 * 7 =49，但 50 比 49 大1。
接着看 8 by 8 magic square。
两个对角的和分别是 (64+1)=65，(57+8)=65。因 8 * 8 =64，但 65 比 64 大1。
接着看 9 by 9 magic square。
两个对角的和分别是 (47+35)=82，(45+27)=82。因 9 * 9 =81，但 82 比 81 大1。
以上大家可以看出一种很奇妙的特性，就是两个各自对角的总和比格子数 (blocks number) 大1。
除了 6 by 6 比较特别。
如果4个角落总和除以2来计算，还是符合大于1的特性。
现在我也可以造出一个符合大于1特性的 6 by 6 magic square。
看新的 6 by 6 magic square。
两个对角的和分别是 (6+31)=37，(1+36)=37。因 6 * 6 =36，但 37 比 36 大1。
现在再回到 communication environment ，如果 sender 在一般的 network 上传送 ciphertext 给 receiver，另外在 secure channel 或是 VPN 上传送 seeds 给 receiver，这个 seeds 就是 magic square 的四个 corner 及 size of base ，当 receiver 收到 sender 所传送的 ciphertext 及 seed 时，receiver 可以利用自行产生一个 magic square，此时，产生的这个 magic square 就是一个 key，利用这个 key 来把 ciphertext 做 decryption，就会得到 plaintext。
For example：
Sender 传送 seeds 为 (9,47,45,37,35) 及 cipertext 给 receiver 时，receiver 收到后，receiver 知道要产生 9 by 9 magic square，且四个corner 一定是 (47,45,37,35)，若不是，receiver 就无法正确的 decrypt ciphertext 为 plaintext。
在【原创】流密码内嵌魔方阵于随机存档之研究-- Magic Square 篇，我所展示的只有用 9 by 9 magic square 来做 encrypt 及decrypt，我是直接告诉您们我用的 是 9 by 9 的 magic square，这次我所介绍的技术与概念是 receiver 自行可以产生 key 来做 decryption，这是目前已知所有的 cryptosystem 所办不到的事。
一个 3 by 3 normal magic square 只有1种，而 4 by 4 normal magic square 有 880 种，可是 5 by 5 normal magic square 却高达 275305224 种。6 by 6 normal magic square 已经是一个 very huge number，而 10 by 10 以上则是 googol number。
这样排列与组合的证明已经有专家及学者证明出来，可以在 How many magic squares are there? 里得到答案。
#include <stdio.h>
#include <stdlib.h>
main()
{ int i,j,x,y,n=2;/* 宣告循环变量i,j,及数组变量x,y,及阶层变量n */
int **magic;/* 宣告数组的大小 */
/* clrscr();/* 消除荧光幕 */ */
while(n>19 || n%2==0){ /* 判断条件是否成立 */
printf("\n 请输入奇数魔术方阵的大小(1-19):");
scanf("%d",&n);
}
magic=(int *)malloc(n* sizeof(int));
*magic=(int *)malloc(n*sizeof(int));
printf("======>%d\n",magic);
x=0;y=(n-1)/2; /* 设定魔术方阵中的第一个位置 */
for(i=0;i<n;i++) /* 将所有的数组设定其值为0 */
for(j=0;j<n;j++)
*(*(magic+i)+j)=0;
*(*(magic+x)+y)=1; /* 设定魔术方阵的第一个值 */
for(i=2;i<=n*n;i++)
{ x=(x+(n-1)) % n; /* 计算方阵往右上的规则 */
y=(y+1) % n; /* 及其x ,y值的变化现象 */
if( (*(*magic+x)+y) != 0){ /* 判断是否会重复 , 如果重复 */
x=((x+2)) % n; /* 计算方阵往下移动到的规则 */
y=(y+(n-1)) % n; /* 及其x ,y值的变化现象 */
}
*(*(magic+x)+y)=i; /* 没有错误,将数字填入魔术方阵中 */
}
printf("--------------%2d阶的魔术方阵------------------\n",n);
for(i=0;i<n;i++){
for(j=0;j<n;j++)
printf("%5d",*((*magic+i)+j));
printf("\n");
}
printf("--------------敬请批评指教--------------------\n");
}
[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法
|
|
|---|---|
|
|
|
|
|
另一处小笔误:
magic=(int *)malloc(n* sizeof(int)); 应该为: magic=(int **)malloc(n* sizeof(int)); for(i=0;i<n;i++) *(magic+i)=(int *)malloc(n*sizeof(int)); 
|
|
|
|
|
|
|
|
|
 对的, 我失误了. 格子数 = n*n . 不等于n的. 呵呵, 我自己粗心了~~ |
|
|
|
|
|
这些附件是根据 【原创】流密码内嵌魔方阵于随机存档之研究 所设计出来的东西。
然后接【原创】流密码内嵌魔方阵于随机存档之研究-- Magic Square 篇 继续讨论。 再继续讨论【原创】流密码内嵌魔方阵于随机存档之研究-- Magic Square 之神奇篇 在这里会是一个 magic square 篇的 final。  上面这个9 by 9 magic square 是由原本的 C program 产生的。 现在我要介绍它的 mutation。 我们知道在 magic square 中最小的是 3 by 3 matrix，如果要产生一个 9 by 9 magic square，其实可以经由 3 by 3 magic square 产生。不必直接产生 9 by 9 magic square。 3 跟 9 的关系，可以看成是 expand 及condense relationship，因此我们可以利用 3 by 3 magic square 的原理，创造出一个9 by 9 magic square。 怎么说呢？ 下面这个彩色的 9 by 9 magic square 就是由 3 by 3 magic square 所 expanded 出来的。 现在我们来看红色粗线，我把它分成一个井字形，或是九宫格。  它总共有九大区块 (9 big blocks)，分别 mark 上不同颜色，每一大区块又可以细分成九小区块 (9 small blocks)。  现在，我们把九大区块分别编号，从(1) 到(9)，再把(1)切割为1到9。 等全部切割完毕，再按顺序从1至81填入9 by 9 magic square。 填完毕后，就大功告成。  我现在用四个 corner 的值来初步验证一下。 (71+11)= 82，(51+31)=82，因 9 * 9 = 81，而 82 比 81 大 1。 符合大于 1 的特性。 验证每一个 column 及 row 或是 cross 的 sum 会不会一样，我就不计算，留给您们自己算。 产生更大的 magic square，可以利用这样的方式依此类推。 关于 magic square topic，我就介绍到这里。 后面若有空，我会回到 stream cipher 的 pseudo random generator 的 topic。 |
|
|
|
|
|
|
|
|
|
|
|
1. 如果Seed与square一一对应，则有固定算法可以从Seed恢复出Key，seed传送过程仍然要保密，因为在密钥体系中的作用一致。其实DES的Key也不是直接拿来去参与Feistel结构的加密过程了了，而是经过了密钥扩展，生成了16轮迭代的子密钥，每个子密钥去参与Feistel中的异或运算。参照DES来看，版主说的Seed更类似与DES的Key，而Square更类似于DES的16轮子密钥。 我在前面的帖子裏就說明了，seeds 要在 secure channel 或是 VPN 裏傳輸，要保護 seeds。 我這裏沒論及 DES ，所以不知道你說的那個情況。 2. 如果不是一一对应的，就不是有无必要Keep secret的问题了，假设A发送了用某个Square_1加密过的密文C(假设明文是M1),同时传给B的还有一个Seed，但是Seed恢复出来的Square_2与Sqare_1不同，就无法保证B可以将C还原了。 這裏，我之前解釋的不是很清楚，讓你誤解，對不起。 我再說明清楚一點： A) 我所謂的不是一一對應，當然不成立，它一定是一一對應的關係。 B) 這麼說好了，以 6 by 6 magic square 為例子，第一個 case 就沒有符合“ 大於1” 的法則，我在第二個 case 才給出另一個 6 by 6 magic square。 以 4 by 4 magic square 為例子，它有 880 種，對於每四個角落的值( 4 corner value) 都只出現過一次，這是不是真的？我也不知道。若是真的，則符合 A) 點，若不為真，則與 A) 矛盾。 C) 表面上看來，“大於1”的法則，並不能完全適用在全部的 magic square；至少我發現在，有好幾組 5 by 5 magic square 上，不符合 “大於1”法則，但確實是一個 normal type 的 5 by 5 magic square。 產生 normal type 的 magic square 有 N 種 algorithm，我也知道其中幾種 algorithm，而我所知道的那些 algorithm，是符合 “大於1”法則的。 以下我給出 5 by 5 不是 “大於1” 的法則。 既然不符合這個法則，那它四個 corner value 當然就不能做為 seeds，可是它依然還是一個 5 by 5 的 normal type magic square。           理論上，我們可以假設 Sender send 一個 4 by 4 magic square's seeds (parameters) 給 Receiver，當 Receiver 收到 seeds 時，他會根據 seeds 去產生一個跟 Sender 一模一樣的 4 by 4 magic square。 這樣的假設很合理，但不實際。 Why？ 因為， Receiver 要知道所有 880 種的 Algorithm，這本身就是一個大問題。 以 Computer 來說，如何 stored 880 種的 Algorithm？ 對 memory space /disk space 等都是困難的工作。 因此，去除這些不符合 “大於1”法則的，某方面是可以解決 memory space/disk space 的難題。 可是又發生一個新問題，什麼問題？ 這樣可能就 insecure。 所以，我才會用 兩道關卡 stream cipher 及 magic square 一起使用。取 stream cipher 及 magic square 它們各自的特性來做成一個很 practical 的 software encryption/decryption. |
|
|
|
