Cryptography-Digest Digest #545, Volume #11 Fri, 14 Apr 00 03:13:01 EDT
Contents:
Re: BlowWire (Paul Rubin)
Re: BlowWire ("Spleen Splitter")
Re: BlowWire (Paul Rubin)
Re: Here's my CHALLANGE!!!! ("Jeff Hamilton")
Re: Q: Entropy (Mok-Kong Shen)
Re: Is AES necessary? (Mok-Kong Shen)
Re: Q: Entropy (Mok-Kong Shen)
Re: BlowWire ("Spleen Splitter")
Re: AND on encrypted data (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: BlowWire
Date: 14 Apr 2000 04:30:42 GMT
In article <3JwJ4.7089$[EMAIL PROTECTED]>,
Spleen Splitter <Spleen*no spam*[EMAIL PROTECTED]> wrote:
>I think I can do this in 60Kgates, with my biggest problem being all
>the simultaneous accesses to pi during each clock (what a ROM, what
>wires!). I'm looking at things like how many register files of how
>many ports, and what sort of ROM in how many copies. Each round
>would presumably be done in a clock, thus leading to the 18 or so
>clock latency to get through the pipe.
>
>Given that I'm only doing Blowfish for fun, I'm fairly certain that
>further enlightenment could be forthcoming on hardware
>implementations of crypto-functions...
It's worse than that. If you look at how the Blowfish key schedule
works, you'll see that the pi table is replaced at key initialization.
You need 4k bytes of *RAM* at each round, not ROM. And if you have
several keys active at the same time, you need another 4k of ram
for each of them.
Blowfish is designed for software implementation and it's inefficient
in hardware. It's not really the right cipher to implement with the
methods you're describing.
There's already a perfectly good cipher (not Blowfish) that was
*designed* for hardware implementation and is extremely well suited to
your approach. People think of it as inefficient because it tends to
be slow when implemented in software; but it wasn't intended for
software implementation. For example, it gets a lot of its diffusion
from bit permutations, which require twisty logic or cumbersome lookup
tables in software, but are trivial (just cross the wires around) in
hardware.
I think you know which cipher I mean. Why don't you use it instead
of Blowfish?
------------------------------
Reply-To: "Spleen Splitter" <Spleen*no spam*[EMAIL PROTECTED]>
From: "Spleen Splitter" <Spleen*no spam*[EMAIL PROTECTED]>
Subject: Re: BlowWire
Date: Fri, 14 Apr 2000 05:25:59 GMT
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:8d66ti$7up$[EMAIL PROTECTED]...
> In article <3JwJ4.7089$[EMAIL PROTECTED]>,
> Spleen Splitter <Spleen*no spam*[EMAIL PROTECTED]> wrote:
> >I think I can do this in 60Kgates, with my biggest problem being all
> >the simultaneous accesses to pi during each clock (what a ROM, what
> >wires!). I'm looking at things like how many register files of how
> >many ports, and what sort of ROM in how many copies. Each round
> >would presumably be done in a clock, thus leading to the 18 or so
> >clock latency to get through the pipe.
> >
> >Given that I'm only doing Blowfish for fun, I'm fairly certain that
> >further enlightenment could be forthcoming on hardware
> >implementations of crypto-functions...
>
> It's worse than that. If you look at how the Blowfish key schedule
> works, you'll see that the pi table is replaced at key initialization.
> You need 4k bytes of *RAM* at each round, not ROM. And if you have
> several keys active at the same time, you need another 4k of ram
> for each of them.
>
> Blowfish is designed for software implementation and it's inefficient
> in hardware. It's not really the right cipher to implement with the
> methods you're describing.
>
> There's already a perfectly good cipher (not Blowfish) that was
> *designed* for hardware implementation and is extremely well suited to
> your approach. People think of it as inefficient because it tends to
> be slow when implemented in software; but it wasn't intended for
> software implementation. For example, it gets a lot of its diffusion
> from bit permutations, which require twisty logic or cumbersome lookup
> tables in software, but are trivial (just cross the wires around) in
> hardware.
>
> I think you know which cipher I mean. Why don't you use it instead
> of Blowfish?
Good info, as I didn't spend much time looking at the intialization
code. But I don't really care about which algorithm, but more about the
implementation. So maybe I'm told to build such a thing is all, or maybe
somebody wants compatibility with a software client on the end of the channel.
In other words, my interest is in the implementation. Number of keys I can
control with some mux's and indexing. So if I need 4KB RAM instead of ROM,
no problem, that's just what I wanted to hear about me making a stupid mistake
right off the bat. But for layout, I'm looking at making 4 copies of the pi
table with 4 banks and 4 ports, 4 copies of the keys in 4 port register files,
and so on, and fun with wires arranging the pipelined rounds in a 2x8 pattern.
So I'm actually looking at 16KB in the pi tables and 4KB in the keys.
I was just curious to hear about other folks trying to implement such things,
since software is too slow, and FPGAs don't quite make it. Better insight into
the algorithm helps, too. Plus, I don't have to worry about how many gates
I burn on this project.
Thanks for taking the time to respond.
cheers,
Spleen Splitter
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: BlowWire
Date: 14 Apr 2000 05:45:10 GMT
In article <HZxJ4.7246$[EMAIL PROTECTED]>,
Spleen Splitter <Spleen*no spam*[EMAIL PROTECTED]> wrote:
>> I think you know which cipher I mean. Why don't you use it instead
>> of Blowfish?
>
>Good info, as I didn't spend much time looking at the intialization
>code. But I don't really care about which algorithm, but more about the
>implementation. So maybe I'm told to build such a thing is all, or maybe
>somebody wants compatibility with a software client on the end of the channel.
If you don't care about which algorithm, why not choose a more suitable one?!
>In other words, my interest is in the implementation. Number of keys I can
>control with some mux's and indexing. So if I need 4KB RAM instead of ROM,
>no problem, that's just what I wanted to hear about me making a stupid mistake
>right off the bat. But for layout, I'm looking at making 4 copies of the pi
>table with 4 banks and 4 ports, 4 copies of the keys in 4 port register files,
>and so on, and fun with wires arranging the pipelined rounds in a 2x8 pattern.
>So I'm actually looking at 16KB in the pi tables and 4KB in the keys.
No I think you don't get it. You start with 4k of ram which is
organized as 4 tables of 32*256 bits. These tables are *initialized*
using digits of pi. Then in key initialization, you stir up the
tables in a key-dependent way, so the resulting tables are totally
different depending on the key. If you want two active keys, you need
two totally separate sets of tables. You only use the digits of pi
when you're initializing the tables during the very slow key setup
operation, so you don't need them in your circuit at all--you can load
them from an external source.
You don't need 4 copies of the pi table or 4 ports--there are 4 separate
tables of 1k each, and they can each live in a separate single ported file,
if I'm using the terms correctly. But you need to replicate the structure
at every round in your pipeline.
I think it would be much more interesting and useful to build a FULLY
pipelined version of triple-DES, with separate S-boxes at each of all
48 rounds, so it's a completely asynchronous circuit (no clocking) whose
speed is limited only by the gate and lookup delays through the pipeline.
------------------------------
From: "Jeff Hamilton" <[EMAIL PROTECTED]>
Subject: Re: Here's my CHALLANGE!!!!
Date: Thu, 13 Apr 2000 23:45:22 -0700
http://jeff28.ath.cx/
I placed the actual Plain-Text and Cipher-Text files up on my website. I
noticed that when I did the cut and paste of them, the post added spaces and
carriage returns. I would hate for someone to complain that they never had a
fair chance to perform an accurate cryptanalysis.
Once again for those of you who think you have the know how..
http://jeff28.ath.cx/
C-ya,
Jeff
"Jeff Hamilton" <[EMAIL PROTECTED]> wrote in message
news:u1wJ4.223$[EMAIL PROTECTED]...
> I posted a message earlier in this month and some of the newsgroup thought
> that they would be willing to try to crack my algorithm just for the fun
of
> it. So here it goes, I'm going to place several chunks of data out
> here...Plain-Text and Cipher-Text as well as the password I used. Cipher 2
> and 3 are the same Plain-Text just different KEYS. There will also be one
> last piece of Cipher-Text which should then be discovered if you can
perform
> cryptanalysis on it. Good luck....
>
> CIPHER 1 Key: this is a simple test
> CIPHER 2 Key: 111111111
> CIPHER 3 Key: 222222222
>
> --------------------------------------Cipher on
> Test1--------------------------------------------
> EL�\ �"�A?hO-l�A"~�H
>
qg".��k��6DT?hEӍ@Jz��ܰ��,<??k�? l^.P��L?C.�9iW�%-"W�.��`5b�ϵ��S�
> �x�'�G�"��ͨ,n7�.��S��"` "�DY��\
> 'd�?85�`m�c��rjF�.ì�<6�0��Q:�������T���r
>
> ��1��`��8Ůd�f
>
> :z��>q�0m�o2;fO�TE^�C~$t�7�cH�-"�A��>b�g� �� ��_�>?d).�wQN� �-I�
> 8�<Q#�I"d;��QSt3���:f�,�-��C8`B_���߸)i��꺹wz TNܐlY9�*
~��ǣ��H8�'
> �/����aqV,�f?�dxT�pz5t��N�n����ߏ�T�`��D#�XS�A�8
> Vq�*pxSs��:#O�&]�c�>��
>
� ?"����g�c=#q?R!w�6z��~R�0u�]�G7���0\L�-2T����)g�ը~`�$�1K?raB�S6�
> �
>
> x��$���۹�o�ǫYK r�w�VS�KDA����2"
>
> ihb�-�D<�ka?�@6��ﰪ>O �^�:.�2���bb�^?:W7�R ��3"�
> �?�MwZ7��]<�n���Q�Z�(����*Z'� i��0��婾�JK����4�X'Td}�j��?�
>
Y�<��T:msh3���nٝ����H/L��-{ˢ#�!�)�e|e>�G�<�:γb,�>/��wwbq"�'Ie��
> #�%<�$�ZU&��"5�*���VSU,mU"- �,t"���j�5�"-f�f�T|ڲm�B�Xx)��bi����
>
> )cEX�SƵ���
>
> �����C�����n�2��ʵ?�
> �g�b��%�?"|��+Li��?�"W�_�>"D�O.CjY��U�85�)= ]�\F\<�,�\�x
> '-)B������.�S�6���q�}�nP(.Z��~L\XK.VG�8�1���-8
> �D�G�<�s�����ʽ�dc.�a�sx�/�?���[MO5�
> ҝ��&��j��/9��D�*:�Xi��Nzv��hr�(` Z��u0ST���H�W���SUpv3~~�
> V�H+���"N+/�m@|
>
> #�%X �e DD2*�)̤�.Ssjv�E.x�Ǥ�>�9>�i�nl=�30
> ;v1X|�>�|�L��?X��EX��+����gA�p� ھZ���(�
> t����@<hpa{3-2S�"�"�7f�m�� i��:�~.�Z�)fC,iY��a�'"3.mh�r< �
>
> T�����x|-��1i�S] �-h��???��Hc���'�/^Yh��{���>{�r�?'�B�9�zR6M
>
> --------------------------------------------------------------------------
--
> -----------------------
>
> ---------------------------------------Plain
> 1-----------------------------------------------------
>
> Path:
>
nntp1-sf.pbi.net!cyclone-backup.sbc.net!cyclone.swbell.net!news.pacbell.net.
> POSTED!not-for-mail
> From: "Jeff Hamilton" <[EMAIL PROTECTED]>
> Newsgroups: sci.crypt
> Subject: Cryptanalysis Challenge - Will anyone accept?
> Lines: 13
> X-Priority: 3
> X-MSMail-Priority: Normal
> X-Newsreader: Microsoft Outlook Express 5.00.2919.6700
> X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6700
> Message-ID: <JVwH4.622$[EMAIL PROTECTED]>
> Date: Fri, 7 Apr 2000 19:45:47 -0700
> NNTP-Posting-Host: 63.197.3.86
> X-Complaints-To: [EMAIL PROTECTED]
> X-Trace: news.pacbell.net 955161321 63.197.3.86 (Fri, 07 Apr 2000 19:35:21
> PDT)
> NNTP-Posting-Date: Fri, 07 Apr 2000 19:35:21 PDT
> Organization: SBC Internet Services
> Xref: cyclone.swbell.net sci.crypt:67820
>
> I was thinking of placing a stream cipher out here that I developed about
3
> years ago. Source and Ciphertext. I was curious if a $100.00 Cryptanalysis
> offer would be sufficient to gain attention. I'm a novice at this and
really
> haven't had a chance to get back in to Cryptography until these last 2
> months.
>
> Would anyone be up to the offer? If so tell me your thoughts. I myself
> already know of it's flaws. Not to mention that some of you who have been
on
> this newsgroup for a while have seen it when I posted it about 3 years
ago.
>
> -Jeff28
>
> --------------------------------------------------------------------------
--
> -------------------------
>
> ------------------The following is the plain-text for both Cipher 2 and
> ---------------------------
>
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
>
1111111111111111111111111111111111111111111111111111111111111111111111111111
> 11111111111111111111111111111111111111111111111111111111
>
> --------------------------------------------------------------------------
--
> ------------------------
>
> -------------------------------------Cipher
> 2-------------------------------------------------------
>
> -Ht*,�/�4V�"�z�#;*?�����:),.T%���I�-�W�X��&!"��o2��,i�'">S�B���
��
> eY<arK�?R.=Q��A�5&K-�:�6u��r��*"��Vô9'k�~.�S'"ջ
> !ML7\�\��L���֬]��~#���p��S�"�^
>
> )�v� -?k�'&�?Gp�<}-�*uz
>
> �W�antz�}"=��ئ�b�o
>
>
u+xNV��?�:x���8-M,�Q�]'�l�8�qa�oy�ɽ3Y��"�Jc)��h��˩~?���գ��.��-�S��[
>
A1����O1�s.�0?���2�D��^���--U��"���o��_��L�/g�H1��GcX�w )�r, [\4�o*B.$�H
> U ��"�(R?,�Y����@�CO�����G�'�-�U�T��Cӵ � �b?#�k@.�B>Q���Z/I�
>
> oOX�1?��^"��hr�"ASA��1�7�< >�K�-a�\O�
> )z`-7IpR]�dt�S�~8���ہ6
> ��T�INb���'nV��e>
>
> �?��"�?
>
> ROE*{�,'���|N.m�m�X�"-�Z1�&��X��A>э��s�.~2 Bc��
> - =6Z,�"XԤ��-rU��h�������AO�t�
>
> �]�gD �-\�*�eQ��C�V�';_~��L4�2�.
> xX?|z��K7�zv����M.�%.%�Ѯ\���eYh��+k/���w
> � ���?��j^S ����
��7\����^���-!?C$sȬ�>�eVL��i�^ZhE��+.�ݸ�-?UN'
> ]�L?����� �|�'[ �Vg��x~
>
>
Ǿ�`3-���EZ/"]GJ�%+����WBs�`?�.�?3 ��*X�D��v'�iv:G�ff�?^�?�t��|s� "+V2�b
> ����"�ZQ��2��~OY
> c>� ��#�S���p?$��Ő
> _�[�o'��7� �4�,���n?��K^o*��-ǡ'dos
>
> �BE~�oo�t�k]����q�3�A,k�gP�>�o?�
Oղop��jx^�ƣF�gH����<"h^�'���<�"�T
> . �[�m�?
>
> �-<m���"1K]:��zS�V��l�,N�
> '�=,WJK܍}_�ΨdTZf6e"ƴ��Ӵ��Ǎo`����A*X7�"vv�K��!s��L-/?�Z4y>l�x
> @��T\��Ft 1]�� �m�;Ѩ��(�U����bY�d,� �q�6l��mJ�F>q�v�?_��))�Nd
>
> H����W�(�ӧ��-��28^ܮ��/�o
>
> ���,?l�)�!M-�'��^�
> ,��GY!h�a�=<I�Y�DZ�B:Ǫ�OϽ!c�)'�߫J+W\|�?PteKWtbI�E,ֲ+�l���T?~��
> ���B9���Msr�^Z�
>
> �V#�`T�-� ��g|�N|Y4e�+?/��"}j�y��| "
> 0H�OSb #�
> �x>ruwTS!x?"F{��x����qJ4<@S�yg 9O��<����M� �?�m4�~3"-�&�sз�g��
>
> lq7��q��Jb^n�H~ʨK��-cZ�s��Iᥐг��'
> ���E�u�$K2�m;�<���k�M�p>X?&`1�<w�!-1��knV?�}俧 �ԥG�'""�^�M�<9�M
��
> S��?,'L�Z��-,`��>�d0��Hr-ಝ���Ec)�Kޝfw�a�
> ���~D%> ��.5 o#Y���S?u���R*O33
>
> 6?�/jN��ڐc
>
> --------------------------------------------------------------------------
--
> ------------------------
>
> -------------------------------------Cipher
> 3-------------------------------------------------------
>
> � \@- �g?��_��~"�-{.>oR9�����
>
> ��Qm�,�~� 4Xs�?&�����5��OZ��-J�'a��_q�zk
>
> S&hF�ud$%��?�qYF�
>
���"���۰AUQ?o@*TTBs�� 6���0��;�5F�2ueq̤5~Ҭ�H?�|�@pߏOE.���b�y<
> ��Тvro�
>
> �S]J���"��1��N +\�>U̹��4
>
> �f?�ʵ?�'^7��s-��T�O�O ��TMԪQ\?#S?�l{�&]�-��e�H��>��^-s�
> (ޤ�oZ7�?<Fs-����Y��%��G(x"=?
>
> �$_��"��G =T�O*���hcOK�أGk�3f�
>
> ����]P��-+E{&Oyi�?�J�r�Q����c�w�,��z
>
> �K"2W,v�UV-t�5B٬^��
X��aiȍ�>����8��n8�}��DNS�-pX��s%��;�#z��"�*/
> 5�s�Qo#H2[=YuU�
>
dJ������-G���A,��#�;?����ĥ]ĸXT�T��B{?N)�nq!����-��fv!��@�]��"]
> �rm�.Ve!w'��I����ة� �h��$�'� +<2�?Q5�O!�C.�-R�r"q~�\�S���c>�
>
> �WG��q@"
>
> 9�fMw�`?+F���(���\' �Th:= ��-
> K�+>���ݍ��.O<EOT7wx�][kS.J�P�O��5��p-*E7V;A�?��AxP���
> H1��
> ���TJ�S*�"T.�Nd�O��n3��-q�o����5J?�KA]���^�?�j��.r<�
> =/Wf�ެ'\�R�0-���T>n��;u�!i�E�'?
~�-.��)�US�|m�|�-�YC���2ml�B&�XN"
> ݝ7X"�4>؝bn
> �th0gw��O.�'�hk��>��'`/�c�DoEg�0TC?��,}K��-�/
>
> "aSEǰ����T[
>
> '�n��S"�ؐ`3)4l,�N�,�Y�ge
>
> f<���
>
> -~)oC?�?�6Z|���.N
> "8z 0XZ��TK'�(�g?:�K�)�l�?I-J�� ?�Q
>
ů��n0�.�vkb$��U�c�wL�&�~��$mQ0�<�H�����>���.�mT�I�p��*^�xJ?�:�9?�
> �^���o[׳'�u
> �skF�>/�,d�.�����bF������Ize��Z�j6,��k�/uʁ�l.Oa��s4/s
> a'W�K���Z+�� p�B��-����
>
> ���}�Y�3+z�� ��^;B�l�G��*B�-�@c{ 5f-1=`YBoi��s
>
> �.��z��U�"6�D�-~Z!L�'?�lI�q"ew�k�֮ ��$��)6�~�@h8�3KHe�s�bb�E���
>
> �"!5�-Ȫ dRZ,�i ?��O7[�O<�'<�.���aWZr\��"O�V��t
>
> �Z
>
> j" ��� �$>y�0�Xe�[2,�SL?�O3fľ\�S
>
> f��vg�U��?�`y�h�w����Kp
>
> DzH����HE�z?����
> ?K���u��%�S�<�t>g��1;=+�U,[p �i?:�x�n�YͺM0�W@��]L��i "8sS�S�K�
> o�, ��|Bz�v\ۨi ��d.Īs�
> S}�l�,��o.��G^?0TVB,6s#?���<J?o��Ŧ=f?.�!b��4�>�U;�f)�
>
> �<
>
> '8�D���a5�O�+�.j��7�?��<���z��"�"�-T^"9]:�:
>
> --------------------------------------------------------------------------
--
> -----------------------
>
> --------------------------------FINAL-------------------------------------
--
> ---------------------
>
> "q1�|W���G-V�%2.KD�?�
>
> o�O�~N�?g����XZ<R�f�Vr?��<4̺1�Ed�Y?�<:�[ɶG~�o;����O-&f�
> Vt��.d�!Y��/����g.?��o$KP ��m���
>
> ��[GK�}S
>
> �v���1�_� �j"�6� ��nw�
>
Q��+qTM2.$���K��\#�f�н*-�7n0����a�l�UcrZ�e-�$lc�-Y�,�i����Y�m�j
> ? ?�Il!�1>7s��~��?�|��;�)DT-.-�I�#r��Tb��C�'�d�� �(t�#�2y&S�7iN�3F�
>
> --------------------------------------------------------------------------
--
> ------------------------
>
>
>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Fri, 14 Apr 2000 08:41:50 +0200
James Felling wrote:
>
> No. What I am saying is:
>
> 1)Over the space of all possible languages, the K-complexity of any finite
> string is 1.( one atomic op will produce that string in some language)
>
> 2) Over a given set of languages L, it is possible to make "K-complexity
> relative to L" comparisons between two strings S1 and S2, but that such
> comparisons are not extensible beyond that specific language family L. ( and
> thus fail to generalize in any meaningful manner -- one can say S1 is shorter
> to code than S2 in language X , but not that S1 is shorter to encode than S2
> in general)
>
> 3) K-complexity for an infinite string is more easily defined, as there are
> infinite strings that are more easily encoded than others. This is true even
> over the space of all languages. ( 000000......) is much more compact
> codewise to generate than the decimal expansion of a trancendental, or
> Chaitin's(sp?) Omega.
> This is where generalized K-complexity has a useful meaning.
Can you confirm the statement that all books discussing K-complexity
of ONE arbitrary (finite) string are doing nonsense? Please
see also what I quoted from a book in a simultaneous response to
Bryan Olson. Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Is AES necessary?
Date: Fri, 14 Apr 2000 08:43:07 +0200
Tom St Denis wrote:
>
> Either DES and RC5 are both resistant to short-cuts, or neither.
If you could give a rigorous proof that two particular modern
ciphers are equally strong, that would be a significant scientific
result and certainly worthy of a journal publication.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Fri, 14 Apr 2000 08:41:41 +0200
Bryan Olson wrote:
>
> > In
> > the few texts that I happened to have glanced at I found that
> > in the definition of the measure the string is said to be
> > 'arbitrary' and there is no mention at all of 'infinite'. Now,
> > according to common (non-explicit) conventions, 'arbitrary' means
> > 'arbitrary finite' if used without explicitly adjoining 'infinite'.
>
> Hard to tell based on a one-word quote, but correct me if
> I'm wrong: the meaning of 'arbitrary' in those definitions
> is in the sense of arbitrarily large. If my interpretation
> is correct on that, then consider the following three
> questions:
>
> Were the million-bit strings in the example arbitrarily
> large? (The example from 2000-04-10 in which I claimed
> Kolmogorov complexity did not say which is more
> complex.)
>
> If you have a finite set of (finite) strings, does it
> contain arbitrarily large strings?
I personally think that it is a rather odd use of the word
'arbitrary' to imply 'arbitrary large' in the context of strings.
Now, I happen to find the following:
For a Turing machine M_i, and a finite string x, the Kolmogorov
complexity of x with respect to M_i is defined as follows:
K_i(x) = min{ l | (ex y) |y| = l and M_i(y) = x }
K_i(x) = infinity if the above set is empty.
on p.70 in O. Watanabe (Ed.) Kolmogorov Complexity and Computational
Comlexity, Springer, 1992.
Here one has only the term 'finite string', should I understand
that the string's length has some implied (not given in the text)
constriants, like the length must exceed certain fixed lower bound,
etc. etc, or does it simply means ANY finite string that one chooses
to pick out and examine? Thanks.
M. K. Shen
------------------------------
Reply-To: "Spleen Splitter" <Spleen*no spam*[EMAIL PROTECTED]>
From: "Spleen Splitter" <Spleen*no spam*[EMAIL PROTECTED]>
Subject: Re: BlowWire
Date: Fri, 14 Apr 2000 06:38:29 GMT
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:8d6b96$sku$[EMAIL PROTECTED]...
> In article <HZxJ4.7246$[EMAIL PROTECTED]>,
> Spleen Splitter <Spleen*no spam*[EMAIL PROTECTED]> wrote:
> >> I think you know which cipher I mean. Why don't you use it instead
> >> of Blowfish?
> >
> >Good info, as I didn't spend much time looking at the intialization
> >code. But I don't really care about which algorithm, but more about the
> >implementation. So maybe I'm told to build such a thing is all, or maybe
> >somebody wants compatibility with a software client on the end of the channel.
>
> If you don't care about which algorithm, why not choose a more suitable one?!
I'm interested in the general mapping of algorithms to hardware. The random
tides swung to Blowfish. I don't care how big it is. The more gates the
example burns the better as far as I'm concerned, as long as the objective
is met.
>
> >In other words, my interest is in the implementation. Number of keys I can
> >control with some mux's and indexing. So if I need 4KB RAM instead of ROM,
> >no problem, that's just what I wanted to hear about me making a stupid mistake
> >right off the bat. But for layout, I'm looking at making 4 copies of the pi
> >table with 4 banks and 4 ports, 4 copies of the keys in 4 port register files,
> >and so on, and fun with wires arranging the pipelined rounds in a 2x8 pattern.
> >So I'm actually looking at 16KB in the pi tables and 4KB in the keys.
>
> No I think you don't get it. You start with 4k of ram which is
> organized as 4 tables of 32*256 bits. These tables are *initialized*
> using digits of pi. Then in key initialization, you stir up the
> tables in a key-dependent way, so the resulting tables are totally
> different depending on the key. If you want two active keys, you need
> two totally separate sets of tables. You only use the digits of pi
> when you're initializing the tables during the very slow key setup
> operation, so you don't need them in your circuit at all--you can load
> them from an external source.
I think we're on the same track. There is a 4KB RAM (not ROM) that maintains
the mishmashed pi/key. It is organized in 4 banks, with each byte of the
round providing the address to a particular bank for the succeeding round.
>
> You don't need 4 copies of the pi table or 4 ports--there are 4 separate
> tables of 1k each, and they can each live in a separate single ported file,
> if I'm using the terms correctly. But you need to replicate the structure
> at every round in your pipeline.
It is the particulars of replicating the structure for supporting the pipeline
that I'm looking into. The 1k tables you mention are the banks I refer to.
First, it appears to me that from looking at a couple of successive rounds:
ROUND (Xr, Xl, 1);
// Xr.word ^= (((bf_S[0][Xl.w.byte0] + bf_S[1][Xl.w.byte1]) ^ bf_S[2][Xl.w.byte2]) +
bf_S[3][Xl.w.byte3]) ^ bf_P[1];
ROUND (Xl, Xr, 2);
// Xl.word ^= (((bf_S[0][Xr.w.byte0] + bf_S[1][Xr.w.byte1]) ^ bf_S[2][Xr.w.byte2]) +
bf_S[3][Xr.w.byte3]) ^ bf_P[2];
...that the tables S and P do not change value between rounds, or through the
data stream-i.e., once initialized they appear to be constant for the duration
of the session. Here, S is the RAM with 4 tables. With 4 ports it services
the next 4 rounds. Then we generate another copy of S for the next four rounds.
This saves space since 4 port widgets are area efficient vs 4 copies of one
port widgets.
>
> I think it would be much more interesting and useful to build a FULLY
> pipelined version of triple-DES, with separate S-boxes at each of all
> 48 rounds, so it's a completely asynchronous circuit (no clocking) whose
> speed is limited only by the gate and lookup delays through the pipeline.
Ok. This can be good, too. I'll go look for the code. Not sure about that
asynchronous stuff, tho. Dynamic logic is getting somewhat out of favor as
we go below 100nm.
cheers,
Spleen Splitter
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: AND on encrypted data
Date: Fri, 14 Apr 2000 08:58:51 +0200
1198 wrote:
>
> Claudio Di Flumeri wrote in message <[EMAIL PROTECTED]>...
> >Does anyone know if there are encryption schemes that allow logical
> >operations (AND, OR, NOT) on encrypted data?
> >
>
> Some opinion here... If you take a close look at XOR operation, with a fix
> key, no two bytes of different values will produce the same result(perfect
> one to one mapping). This is not true with AND or OR. (NOT is a special case
> of XOR, XOR with $FF ). So you see more XOR used in encryption than others
> in simple cases. Sure you can use AND or OR (even rotate, but it need less
> care as XOR) in your scheme but you need more care so you can be sure that
> in no case you encrypted data cannot be recovered.
In my humble view, it isn't of much value to draw a sharp division
line between logical and arithmetic (integer) operations, if they
are of about the same speed (this is mostly the case, if I don't
err). It thus depends solely on the actual need of the design to
determine which operations get used. Because of its simple inversion
property, XOR is the most commonly used logical operation in
encryption algorithms. I personally prefer, however, an arithmetic
add over XOR, for the former effects a certain diffusion of bits
due to carry-overs.
M. K. Shen
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
