home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / crypt / 6267 < prev    next >
Encoding:
Text File  |  1992-12-29  |  4.1 KB  |  105 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!newsgate.watson.ibm.com!yktnews!admin!wo0z!lwloen
  3. From: lwloen@rchland.vnet.ibm.com (Larry Loen)
  4. Subject: Re: perfect secrecy
  5. Sender: news@rchland.ibm.com
  6. Message-ID: <1992Dec29.152217.23308@rchland.ibm.com>
  7. Date: Tue, 29 Dec 1992 15:22:17 GMT
  8. Reply-To: lwloen@rchland.vnet.ibm.com
  9. Disclaimer: This posting represents the poster's views, not necessarily those of IBM
  10. References:  <1992Dec29.121656.4726@nuscc.nus.sg>
  11. Nntp-Posting-Host: wo0z.rchland.ibm.com
  12. Organization: IBM Rochester
  13. Lines: 90
  14.  
  15. In article <1992Dec29.121656.4726@nuscc.nus.sg>, isc40019@nusunix1.nus.sg (THAI LING) writes:
  16. |> I think this is a neat folder to discuss topics on cyptography.
  17. |> I am currently doing a course on it and there are some questions 
  18. |> on my mind.Can anyone help?
  19. |> 
  20. |> Does anyone know how to prove the following :
  21. |> 
  22. |> Q1 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
  23. |> Definition : M = the message space
  24. |>              K = the key space
  25. |>              C = the cytogram space 
  26. |>  ! ! means the cardinality of
  27. |> 
  28. |> Given that !M! = !K! = !C! then perfect secrecy is achieved if
  29. |> 
  30. |> (1) all the keys are equiprobable
  31. |> (2) there is exactly one transformation ( i.e one key ) from a given
  32. |>     message to a given cyptogram
  33. |> 
  34.  
  35. If this is meant for an arbitrary cryptosystem, it is easily _disproven_.
  36.  
  37. Suppose one has the well-broken cryptosystem that uses a "random" number
  38. generator of the form  x(n+1) = (A * x(n)  + C)   mod M and that the
  39. cipher text is formed by exclusive orring successive terms of x with
  40. the plaintext.
  41.  
  42. Suppose further that the value of  x(0) (that is, the first term) is
  43. chosen by flipping a perfectly balanced coin to establish each bit
  44. in x's representation.
  45.  
  46. Now, if A, M, and C are correctly chosen (all relatively prime to each
  47. other, if memory serves and this is usual for such a system), each value
  48. from 0...M-1 will appear exactly once.  Now, since the plaintext is 
  49. broken into groups of size M as well, it appears to me that the 
  50. conditions described above have been achieved if one presumes a general
  51. enough plaintext to admit all 0...M-1 values, which is also usual.
  52.  
  53. Yet, this system is well-studied and can be broken (for example) if
  54. A, C, and M are known (usual crypto assumptions) and if two successive
  55. values of the plaintext can be guessed using ordinary algebra.  There
  56. are also breaks relating to the problem that there may be two messages
  57. who share values of x.
  58.  
  59. At best, the conditions you cite are "necessary", but are certainly not
  60. "sufficient".  They probably are not even "necessary".
  61.  
  62. |> Q2 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
  63. |> 
  64. |> how can the key space be increased by using a combination of keys are
  65. |> encryption instead of a single key replacement?
  66. |> i.e instead of A   ......  B
  67. |>                .          .
  68. |>                .          .
  69. |>                .          .
  70. |>                .          .
  71. |>                Z           K
  72. |> 
  73. |> to try        AB  .......   CD
  74. |>                .          .
  75. |>                .          .
  76. |>                .          .
  77. |>                .          .
  78. |>               AZ   ......   WE  ...etc
  79. |>  
  80. |> Thanks in advance !!!!!
  81. |> 
  82. |> Linda
  83.  
  84. If I understand your question, the answer is very specific to the
  85. system.  For instance, in DES, it can be shown that an "enhanced" 
  86. DES using two keys done like so:
  87.  
  88.       E(k1,E(k2,x)) 
  89.  
  90.  can be defeated in only about double the number of
  91.  operations rather that 2 to the 110 operations as might be guessed
  92.  if one is granted the luxury of a table of size 2 to the 67th bytes.
  93.  
  94.  
  95. If you don't mind my asking, what cryptography books do you have available
  96. to you?  These questions should be able to be ferreted out of available
  97. sources (such as H. F. Gaines' "Cryptanalysis").  On the other hand,
  98. I have no idea what restrictions one labors under outside of the US.
  99. (If you choose not to answer this question, I will understand; I really
  100. _don't_ know what restrictions you labor under and it is sometimes a
  101. mistake to even ask).
  102. -- 
  103.    Larry W. Loen        |  My Opinions are decidedly my own, so please
  104.                         |  do not attribute them to my employer
  105.