我和我追逐的梦

似曾相恋转眼过往已云烟 惋惜多情已经从前

[算法]利用矩阵乘法实现简单加密

Saturday
Oct 4,2008

原理：设有明文字串矩阵S，初始矩阵M，则加密过程为 M * S = N，其中N为密文矩阵。解密过程则为 (M-1) * N = S。

于是乎，只要找到一个n阶矩阵M(n X n)，字串矩阵S可以取自某一段文本的ASCII码，把他写成符合于M做矩阵乘法的格式就是S(n X 1)。所以，假设S的明文字符个数为m个，于是只要做(m / n)次和M的矩阵乘法即可得到密文。当然，这里的m可能为奇数或者偶数，所以可能会余留一个字符。遂欲得到密文矩阵N的明文字串的话，只要把密文矩阵N与初始矩阵M的逆矩阵(M-1)做矩阵乘法即可，最终可以得到明文字串S。所以M即是SN之间的钥匙。得到的N的复杂度和M的阶数以及内容有关。作为钥匙，M不可以取定值，最好是通过有用户输入一段密码来生成初始矩阵M，解密的时候再次输入密码生成M，之后再计算(M-1)。

关于求逆矩阵和矩阵乘法的Code，参见前2篇post。

Tags: , ,
  • 0 Comments

    • [算法]矩阵乘法

    Saturday
    Oct 4,2008

    关键部分的代码：

    假设a[N][M] * b[M][K] = c[N][K];

    1. for (i = 0; i < 2; i++) 
    2.         for (j = 0; j < 3; j++)
    3.             for (z = 0; z < 2; z++)
    4.             {
    5.                 c[i][z] = c[i][z] + a[i][j] * b[j][z];
    6.             }
    Tags: , ,
  • 0 Comments

    • [算法]求逆矩阵(高斯-约旦法)

    Saturday
    Oct 4,2008
    下载: matrixreverse.c
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3.  
    4. double *matrixreverse(double A[], int m, int n);
    5. double *matrixinver(double A[], int m, int n);
    6. double surplus(double A[], int m, int n) ;
    7.  
    8. int main()
    9. {
    10.     int m = 2, n = 2;
    11.     int i;
    12.     double* A = NULL;
    13.     double* RST = NULL;
    14.     A = (double*)malloc(m * n * sizeof(double));
    15.     RST =  (double*)malloc(m * n * sizeof(double));
    16.     for (i = 0; i < m * n; i++)
    17.     {
    18.         scanf("%lf", &A[i]);
    19.     }
    20.    
    21.     RST = matrixreverse(A, m, n);
    22.    
    23.     for (i = 0; i < m * n; i++)
    24.     {
    25.         printf("%lf\t", RST[i]);
    26.     }
    27.    
    28.     printf("\n");
    29.     //system("pause");
    30.     return 0;
    31. }
    32.  
    33. double *matrixreverse(double A[], int m, int n) /*矩阵求逆*/
    34. {
    35.         int i, j, x, y, k;
    36.         double *SP = NULL, *AB = NULL, *B = NULL, X, *C;
    37.         SP = (double*)malloc(m * n * sizeof(double));
    38.         AB = (double*)malloc(m * n * sizeof(double));
    39.         B = (double*)malloc(m * n * sizeof(double));
    40.  
    41.         X = surplus(A,m,n);
    42.         X = 1 / X;
    43.         for (i = 0; i < m; i++)
    44.                 for(j = 0; j < n; j++)
    45.                 {
    46.                         for(k = 0; k < m * n; k++)
    47.                                 B[k] = A[k];
    48.                         {
    49.                                 for(x = 0; x < n; x++)
    50.                                         B[i * n + x] = 0;
    51.                                 for(y = 0; y < m; y++)
    52.                                         B[m * y + j] = 0;
    53.                                 B[i * n + j] = 1;
    54.                                 SP[i * n + j] = surplus(B, m, n);
    55.                                 AB[i * n + j] = X * SP[i * n + j];
    56.                         }
    57.                 }
    58.                 C = matrixinver(AB, m, n);
    59.    
    60.         return C;
    61. }
    62.  
    63. double *matrixinver(double A[], int m, int n) /*矩阵转置*/
    64. {
    65.         int i, j;
    66.         double *B = NULL;
    67.         B =(double*)malloc(m * n * sizeof(double));
    68.  
    69.         for(i = 0; i < n; i++)
    70.                 for(j = 0; j < m; j++)
    71.                         B[i * m + j] = A[j * n + i];
    72.         return B;
    73. }
    74.  
    75. double surplus(double A[], int m, int n) /*求矩阵行列式*/
    76. {
    77.         int i, j, k, p, r;
    78.         double X, temp = 1, temp1 = 1, s = 0, s1 = 0;
    79.  
    80.         if (n == 2)
    81.         {
    82.                 for (i = 0; i < m; i++)
    83.             for (j = 0; j < n; j++)
    84.                 if ((i + j) % 2) 
    85.                     temp1 *= A[i * n + j];
    86.                 else 
    87.                     temp *= A[i * n + j];
    88.         X = temp - temp1;
    89.     }
    90.     else
    91.     {
    92.         for (k = 0; k < n; k++)
    93.         {
    94.             for (i = 0, j = k; i < m, j < n; i++, j++)
    95.                 temp *= A[i * n + j];
    96.             if (m - i)
    97.             {
    98.                 for (p = m - i, r = m - 1; p > 0; p--, r--)
    99.                     temp *= A[r * n + p - 1];
    100.             }
    101.             s += temp;
    102.             temp = 1;
    103.         }
    104.  
    105.         for (k = n - 1; k >= 0; k--)
    106.         {
    107.             for (i = 0, j = k; i < m, j >= 0; i++, j--)
    108.                 temp1 *= A[i * n + j];
    109.             if (m - i)
    110.             {
    111.                 for (p = m - 1, r = i; r < m; p--, r++)
    112.                     temp1 *= A[r * n + p];
    113.             }
    114.             s1 += temp1;
    115.             temp1 = 1;
    116.         }
    117.        
    118.         X = s - s1;
    119.     }
    120.    
    121.     return X;
    122. }
    Tags: , ,
  • 1 Comment

    • char[]型IP地址到16进制的unsigned long型的转换

    Thursday
    Sep 18,2008

    主机字节序和网络字节序的转换只要更改p[]的顺序即可。

    1. unsinged long int ipstring2long(const char *ipstr)
    2. {
    3.     int  ip[4];
    4.     int  matches;
    5.     unsinged long int tmp;
    6.     unsigned char   *p = (unsigned char*)&tmp;
    7.  
    8.     matches = sscanf(ipstr, "%u.%u.%u.%u", &ip[0], &ip[1], &ip[2], &ip[3]);
    9.     if ( matches != 4 )
    10.     {
    11.         return (unsigned long int) - 1;
    12.     }
    13.     else 
    14.     {
    15.         p[3] = ip[0];
    16.         p[2] = ip[1];
    17.         p[1] = ip[2];
    18.         p[0] = ip[3];
    19.         return tmp;
    20.     }
    21.  
    22. }
    Tags: ,
  • 1 Comment

    • Recent Posts

    Calendar

      September 2010
      M T W T F S S
      « Jul    
       12345
      6789101112
      13141516171819
      20212223242526
      27282930  

    Archives

    Links

    Tag Cloud

    About Me

      ID：Matrix Chou
      QQ：64502411
      Skype: choukuangjay
      Twitter: andylog
      Writing USB 3G Card Driver For Router/ADSL


    Recent Comments



    Blog联播



    Visitors From

    free counters


    Subscription

    Copyright © 2005-2008 - 我和我追逐的梦 - is powered by WordPress
      Generate Time: 1.436 Seconds