Cryptography-Digest Digest #147, Volume #10 Tue, 31 Aug 99 02:13:03 EDT
Contents:
Re: 512 bit number factored (Paul Rubin)
Re: What if RSA / factoring really breaks? (Paul Rubin)
Re: What if RSA / factoring really breaks? (John Savard)
Re: Which of these books are better ?
HIV testing ( Doug Goncz)
Re: WT Shaw temporarily sidelined
Re: original source code for robert morris crypt.c circa 1970's (Dennis Ritchie)
Re: n-ary Huffman Template Algorithm (Alex Vinokur)
Re: n-ary Huffman Template Algorithm (Alex Vinokur)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: 512 bit number factored
Date: 31 Aug 1999 04:20:26 GMT
In article <7qeu5m$csg$[EMAIL PROTECTED]>, Bob Silverman <[EMAIL PROTECTED]> wrote:
>[some nostalgia: anyone lse remember ihnp4 as a major node on
>the net prior to 1984's revision of internet adressing]
Yes.
-- Paul
...ihnp4!allegra!phr ;-)
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Crossposted-To: alt.math,sci.math
Subject: Re: What if RSA / factoring really breaks?
Date: 31 Aug 1999 05:20:22 GMT
In article <7qeh7s$2pq$[EMAIL PROTECTED]>, Bob Silverman <[EMAIL PROTECTED]> wrote:
>> because public key encryption can now be
>> broken in real time with Bill Payne's recent advances in factoring.
>
>Where did he publish his results? Neither I, nor any other
>factoring expert has ever seen his paper.
It was here on sci.crypt a few years ago. Don't worry, you didn't
miss anything ;-).
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: What if RSA / factoring really breaks?
Date: Mon, 30 Aug 1999 18:27:36 GMT
Bob Silverman <[EMAIL PROTECTED]> wrote, in part:
>In article <7qc4rb$4gl$[EMAIL PROTECTED]>,
> David A Molnar <[EMAIL PROTECTED]> wrote:
>> The joke will be on us if
>> discrete log is easy and factoring is hard.
>This is unlikely.
I vaguely recall reading a claim somewhere that a fast discrete log
algorithm could actually be used to speed up factoring. (Which implies
that it's already known that discrete log is at least as hard as
factoring.) Is my memory playing tricks on me again?
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Which of these books are better ?
Date: 31 Aug 99 05:07:01 GMT
JaeYong Kim ([EMAIL PROTECTED]) wrote:
: for both conceptional understanding and mathematical understanding..
: 1. Applied Cryptography, Bruce Schneier
: 2. Handbook of Applied cryptography, Menezes et al
: 3. Cryptography: Theory and Practice, Stinson
I can understand your question; they are (moderately) expensive books.
3 is the oldest, and 2 the most recent.
I haven't seen 3, but I do know it's organized so that it can be used as a
textbook. 1 is very popular, very approachable, and contains an excellent
body of citations as a guide for further reading. But it doesn't explain
all the math by itself. 2, of course, you have the opportunity to evaluate
for yourself. It doesn't cover as many block ciphers as 1, but otherwise
it seems to be closer to what you are looking for.
John Savard
------------------------------
From: [EMAIL PROTECTED] ( Doug Goncz )
Subject: HIV testing
Date: 31 Aug 1999 05:35:45 GMT
There was a little local news coverage of DC's HIV policy. They wanted to know
if they should keep names and HIV status in a secure computer. I think they
decided not to.
I belive it would be useful, and might be acceptable to the general public, to
maintain a file of people's DNA fingerprints associated with their HIV status.
The fingerprints cost more than the HIV test.
I wrote earlier about possiblities for an STD database.
I guess even a person's DNA fingerprint can be taken against their will, using
a blood sample taken without consent. So that would circumvent the security of
the database.
There is no newsgroup to discuss social implications of cryptographic
technology, as far as I know.
So I'm putting this here.
Yours,
Doug Goncz,
Experimental Machinist ( DOT 600.260-022 ) ( A.A.S.M.E.T. )
Replikon Research ( USA 22044-0094 )
http://users.aol.com/DGoncz or /ReplikonVA
Self Reproducing Machine Tools
Wacky Propulsion Concepts
Dog Walking
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: WT Shaw temporarily sidelined
Date: 31 Aug 99 04:56:06 GMT
SCOTT19U.ZIP_GUY ([EMAIL PROTECTED]) wrote:
: what is IIRC and by advanced age do you mean older than 70.
If I remember correctly, and yes.
John Savard
------------------------------
From: Dennis Ritchie <[EMAIL PROTECTED]>
Subject: Re: original source code for robert morris crypt.c circa 1970's
Date: Tue, 31 Aug 1999 06:04:59 +0100
Reply-To: [EMAIL PROTECTED]
dan braun asked:
>
> Does anybody have a copy of the original (circa 1970?) source code for
> robert h. morris' crypt.c?
> thanks in advance
> dan
Yes, at least snapshots. The first use of encryption in Unix
was for password hashing and it wasn't in C, but PDP-11
assembler, and it was a modified version of the Hagelin
M-209 mechanical polyalphabetic scheme.
The first crypt command was in the Sixth Edition distribution
(May 1975), and it begins with the comment
/*
This routine is an exact implementation of Boris Hagelin's
cryptographic machine. See U. S. Patent #2089603.
*/
However, it wasn't documented in the printed manual,
probably just because Bob didn't bother to write
a man page. Also, "exact" isn't exactly correct.
I think it does reproduce what an M-209 would do on
alphabetics.
Dennis
------------------------------
From: Alex Vinokur <[EMAIL PROTECTED]>
Crossposted-To: sci.image.processing,sci.math,alt.comp.compression
Subject: Re: n-ary Huffman Template Algorithm
Date: Tue, 31 Aug 1999 05:39:06 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Alex Vinokur wrote:
>
> > 2. Huffman template algorithm enables
> > to use non-numerical weights (costs, frequences).
>
> A question just for my understanding: How can frequencies be
> non-numerical at all? If you have a number of frequencies and have
> only their ordering according to magnitude but not know their
> numerical values, how can you expect to obtain a coding that is
> optimal?
>
> M. K. Shen
>
Alex Vinokur wrote
==========================================================
news:comp.theory
1999/02/23
http://www.deja.com/=dnc/[ST_rn=ps]/getdoc.xp?AN=447456922
==========================================================
>
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> >
> > > The question is :
> > > Does anybody see theoretical/applied significance
> > > of non-numerical cost type in Huffman codes (algorithm)?
> >
> > dear Alex,
> > could you explain what you mean by cost????
> > Otherwise your post is too costly for me...
> >
> > --
> > P. Meyer
> > Universite de Paris Sud
> > Physique des Solides, bt. 510
> > e-mail : [EMAIL PROTECTED]
> > T : (33) (0)1 69 15 60 62
> > Fx: (33) (0)1 69 15 60 68
> >
>
>
>
> Hi,
>
> Thank you very much.
>
>
> //================================================
>
> Huffman codes.
>
> word a1 a2 a3 a4 a5 a6
> cost c1 c2 c3 c4 c5 c6
>
> When working with costs (c1, c2, ...)
> Huffman algorithm uses
> operator< (i.e. to compare two costs)
> and
> operator+ (e.g. to add two costs).
>
>
> We know how to compare and to add
> i) integer costs (the cost type is integer number)
> ii) costs in floating-point arithmetic (the cost type is float
number).
>
>
> 1. Huffman codes with integer cost.
> Example
>
> word a1 a2 a3 a4 a5 a6
> int cost 5 9 11 12 127 331
>
>
>
> 2. Huffman codes with float cost (e.g. probabilities).
> Example
>
> word a1 a2 a3 a4 a5 a6
> float cost 0.02 0.12 0.14 0.15 0.22 0.35
>
> //================================================
>
> So from Huffman algorithm point of view
> it is not important what type of cost is.
> The algorithm is using only operator< and operator+.
>
>
> Now we can write Huffman algorithm in C++ language, using templates.
>
>
> ################################################################
> ################### HuffmanTemplateAlgorithm ###################
> ################################################################
>
> ======================= program (BEGIN) =======================
>
> #include <stl.h>
>
> //----------- template class Node -----------
> template <typename WODR_TYPE, typename COST_TYPE>
> class Node
> {
> private :
> WODR_TYPE word_;
> COST_TYPE cost;
>
> // omitted
> };
>
> //----------- template class Tree -----------
> template <typename WODR_TYPE, typename COST_TYPE>
> class Tree
> {
> // Node<WODR_TYPE, COST_TYPE> is used
> // omitted
>
> COST_TYPE& getTreeCost () const
> {
> // omitted
> };
> };
>
>
> //----------- HuffmanTemplateAlgorithm function -----------
> template <typename WODR_TYPE, typename COST_TYPE>
> Tree<WODR_TYPE, COST_TYPE> HuffmanTemplateAlgorithm (
> const vector<WODR_TYPE>& words_i,
> const vector<COST_TYPE>& costs_i
> )
> {
> // omitted
> } // void HuffmanTemplateAlgorithm
>
>
> //----------- class myCostType -----------
> class myCostType
> {
> // omitted
>
> bool operator< (const myCostType& value_i)
> {
> // omitted
> };
>
> myCostType& operator+ (const myCostType& value_i)
> {
> // omitted
> };
> };
>
> //----------------------------
> //----------- main -----------
> //----------------------------
> int main ()
> {
> //-------------------
> vector<string> words;
> words.push_back ("a1");
> words.push_back ("a2");
> words.push_back ("a3");
> words.push_back ("a4");
> words.push_back ("a5");
> words.push_back ("a6");
>
> //-------------------
> //---- int costs ----
> //-------------------
> vector<int> int_costs;
> int_costs.push_back (5);
> int_costs.push_back (9);
> int_costs.push_back (11);
> int_costs.push_back (12);
> int_costs.push_back (127);
> int_costs.push_back (331);
>
> Tree<string, int> Tree_with_int_cost =
> HuffmanTemplateAlgorithm<string, int> (words, int_costs);
>
> cout << "Total cost of Tree_with_int_cost = "
> << Tree_with_int_cost.getTreeCost ()
> << endl;
>
>
> //-------------------
> //---- float costs --
> //-------------------
> vector<float> float_costs;
> float_costs.push_back (0.02);
> float_costs.push_back (0.12);
> float_costs.push_back (0.14);
> float_costs.push_back (0.15);
> float_costs.push_back (0.22);
> float_costs.push_back (0.35);
>
> Tree<string, float> Tree_with_float_cost =
> HuffmanTemplateAlgorithm<string, float> (words, float_costs);
>
> cout << "Total cost of Tree_with_float_cost = "
> << Tree_with_float_cost.getTreeCost ()
> << endl;
>
>
>
> //--------------------
> //- myCostType costs -
> //--------------------
> vector<myCostType> myCostType_costs;
> myCostType_costs.push_back (myCostType (...));
> myCostType_costs.push_back (myCostType (...));
> myCostType_costs.push_back (myCostType (...));
> myCostType_costs.push_back (myCostType (...));
> myCostType_costs.push_back (myCostType (...));
> myCostType_costs.push_back (myCostType (...));
> // Note! instead of ... the constructor input parameters must
be
>
> Tree<string, myCostType> Tree_with_myCostType_cost =
> HuffmanTemplateAlgorithm<string, myCostType> (words,
myCostType_costs);
>
> cout << "Total cost of Tree_with_myCostType_cost = "
> << Tree_with_myCostType_cost.getTreeCost ()
> << endl;
>
>
> //---------------
> //---------------
> //---------------
> return 0;
> }
>
>
> ======================= program (END)) ========================
>
> So HuffmanTemplateAlgorithm can work with any cost type
> with determined operator< and operator+.
>
>
> 3. Huffman codes with myCostType cost.
> Example
>
> word a1 a2 a3 a4 a5 a6
> myCostType cost .. .. .. .. .. ..
>
>
>
> =====================================
> =====================================
> =====================================
>
> Thus, cost type is any type with determinated operator< and operator+.
>
>
> Crosbie Fitch <[EMAIL PROTECTED]> wrote :
>
> [snip]
> > But when you say non-numerical cost, I can only presume you mean
something
> > like political cost, e.g. encoding choice determined by whether a
bunch of
> > voters fund one representation more aesthetic than the other (but
the vote's
> > still numerical).
> >
> > Perhaps you're using a high-level, esoteric mathematical language
that only
> > appears to be accessible to mere mortals such as I (who thought we
knew how
> > Huffman encoding worked)... in which case disregard this posting.
> [snip]
>
> Thank you very much.
>
> I don't mean anything concrete.
> I'm only asking.
> I would like to know can HuffmanTemplateAlgorithm be used (useful).
>
> The point is :
> Are new theoretical/applied significant cost types
> for Huffman codes existing (used)?
>
> Thanks,
> Alex
>
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Alex Vinokur <[EMAIL PROTECTED]>
Crossposted-To: sci.image.processing,sci.math,alt.comp.compression
Subject: Re: n-ary Huffman Template Algorithm
Date: Tue, 31 Aug 1999 05:40:02 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Alex Vinokur wrote:
>
> > 2. Huffman template algorithm enables
> > to use non-numerical weights (costs, frequences).
>
> A question just for my understanding: How can frequencies be
> non-numerical at all? If you have a number of frequencies and have
> only their ordering according to magnitude but not know their
> numerical values, how can you expect to obtain a coding that is
> optimal?
>
> M. K. Shen
>
Alex Vinokur wrote
==========================================================
news:comp.theory
1999/02/23
http://www.deja.com/=dnc/[ST_rn=ps]/getdoc.xp?AN=447456922
==========================================================
>
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> >
> > > The question is :
> > > Does anybody see theoretical/applied significance
> > > of non-numerical cost type in Huffman codes (algorithm)?
> >
> > dear Alex,
> > could you explain what you mean by cost????
> > Otherwise your post is too costly for me...
> >
> > --
> > P. Meyer
> > Universite de Paris Sud
> > Physique des Solides, bt. 510
> > e-mail : [EMAIL PROTECTED]
> > T : (33) (0)1 69 15 60 62
> > Fx: (33) (0)1 69 15 60 68
> >
>
>
>
> Hi,
>
> Thank you very much.
>
>
> //================================================
>
> Huffman codes.
>
> word a1 a2 a3 a4 a5 a6
> cost c1 c2 c3 c4 c5 c6
>
> When working with costs (c1, c2, ...)
> Huffman algorithm uses
> operator< (i.e. to compare two costs)
> and
> operator+ (e.g. to add two costs).
>
>
> We know how to compare and to add
> i) integer costs (the cost type is integer number)
> ii) costs in floating-point arithmetic (the cost type is float
number).
>
>
> 1. Huffman codes with integer cost.
> Example
>
> word a1 a2 a3 a4 a5 a6
> int cost 5 9 11 12 127 331
>
>
>
> 2. Huffman codes with float cost (e.g. probabilities).
> Example
>
> word a1 a2 a3 a4 a5 a6
> float cost 0.02 0.12 0.14 0.15 0.22 0.35
>
> //================================================
>
> So from Huffman algorithm point of view
> it is not important what type of cost is.
> The algorithm is using only operator< and operator+.
>
>
> Now we can write Huffman algorithm in C++ language, using templates.
>
>
> ################################################################
> ################### HuffmanTemplateAlgorithm ###################
> ################################################################
>
> ======================= program (BEGIN) =======================
>
> #include <stl.h>
>
> //----------- template class Node -----------
> template <typename WODR_TYPE, typename COST_TYPE>
> class Node
> {
> private :
> WODR_TYPE word_;
> COST_TYPE cost;
>
> // omitted
> };
>
> //----------- template class Tree -----------
> template <typename WODR_TYPE, typename COST_TYPE>
> class Tree
> {
> // Node<WODR_TYPE, COST_TYPE> is used
> // omitted
>
> COST_TYPE& getTreeCost () const
> {
> // omitted
> };
> };
>
>
> //----------- HuffmanTemplateAlgorithm function -----------
> template <typename WODR_TYPE, typename COST_TYPE>
> Tree<WODR_TYPE, COST_TYPE> HuffmanTemplateAlgorithm (
> const vector<WODR_TYPE>& words_i,
> const vector<COST_TYPE>& costs_i
> )
> {
> // omitted
> } // void HuffmanTemplateAlgorithm
>
>
> //----------- class myCostType -----------
> class myCostType
> {
> // omitted
>
> bool operator< (const myCostType& value_i)
> {
> // omitted
> };
>
> myCostType& operator+ (const myCostType& value_i)
> {
> // omitted
> };
> };
>
> //----------------------------
> //----------- main -----------
> //----------------------------
> int main ()
> {
> //-------------------
> vector<string> words;
> words.push_back ("a1");
> words.push_back ("a2");
> words.push_back ("a3");
> words.push_back ("a4");
> words.push_back ("a5");
> words.push_back ("a6");
>
> //-------------------
> //---- int costs ----
> //-------------------
> vector<int> int_costs;
> int_costs.push_back (5);
> int_costs.push_back (9);
> int_costs.push_back (11);
> int_costs.push_back (12);
> int_costs.push_back (127);
> int_costs.push_back (331);
>
> Tree<string, int> Tree_with_int_cost =
> HuffmanTemplateAlgorithm<string, int> (words, int_costs);
>
> cout << "Total cost of Tree_with_int_cost = "
> << Tree_with_int_cost.getTreeCost ()
> << endl;
>
>
> //-------------------
> //---- float costs --
> //-------------------
> vector<float> float_costs;
> float_costs.push_back (0.02);
> float_costs.push_back (0.12);
> float_costs.push_back (0.14);
> float_costs.push_back (0.15);
> float_costs.push_back (0.22);
> float_costs.push_back (0.35);
>
> Tree<string, float> Tree_with_float_cost =
> HuffmanTemplateAlgorithm<string, float> (words, float_costs);
>
> cout << "Total cost of Tree_with_float_cost = "
> << Tree_with_float_cost.getTreeCost ()
> << endl;
>
>
>
> //--------------------
> //- myCostType costs -
> //--------------------
> vector<myCostType> myCostType_costs;
> myCostType_costs.push_back (myCostType (...));
> myCostType_costs.push_back (myCostType (...));
> myCostType_costs.push_back (myCostType (...));
> myCostType_costs.push_back (myCostType (...));
> myCostType_costs.push_back (myCostType (...));
> myCostType_costs.push_back (myCostType (...));
> // Note! instead of ... the constructor input parameters must
be
>
> Tree<string, myCostType> Tree_with_myCostType_cost =
> HuffmanTemplateAlgorithm<string, myCostType> (words,
myCostType_costs);
>
> cout << "Total cost of Tree_with_myCostType_cost = "
> << Tree_with_myCostType_cost.getTreeCost ()
> << endl;
>
>
> //---------------
> //---------------
> //---------------
> return 0;
> }
>
>
> ======================= program (END)) ========================
>
> So HuffmanTemplateAlgorithm can work with any cost type
> with determined operator< and operator+.
>
>
> 3. Huffman codes with myCostType cost.
> Example
>
> word a1 a2 a3 a4 a5 a6
> myCostType cost .. .. .. .. .. ..
>
>
>
> =====================================
> =====================================
> =====================================
>
> Thus, cost type is any type with determinated operator< and operator+.
>
>
> Crosbie Fitch <[EMAIL PROTECTED]> wrote :
>
> [snip]
> > But when you say non-numerical cost, I can only presume you mean
something
> > like political cost, e.g. encoding choice determined by whether a
bunch of
> > voters fund one representation more aesthetic than the other (but
the vote's
> > still numerical).
> >
> > Perhaps you're using a high-level, esoteric mathematical language
that only
> > appears to be accessible to mere mortals such as I (who thought we
knew how
> > Huffman encoding worked)... in which case disregard this posting.
> [snip]
>
> Thank you very much.
>
> I don't mean anything concrete.
> I'm only asking.
> I would like to know can HuffmanTemplateAlgorithm be used (useful).
>
> The point is :
> Are new theoretical/applied significant cost types
> for Huffman codes existing (used)?
>
> Thanks,
> Alex
>
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
** 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
******************************
