Cryptography-Digest Digest #125, Volume #9 Tue, 23 Feb 99 10:13:03 EST
Contents:
Re: VxD Crypto - Win 95/98/NT (Anthony Naggs)
Re: Huffman codes with non-numerical cost? (Alex Vinokur)
Re: Testing Algorithms (fungus)
Re: Testing Algorithms (fungus)
Re: Interesting DES results
Re: Interesting DES results
Re: Testing Algorithms (Patrick Juola)
Re: Visual Cryptography ("Scott Berg")
signcode, password ("gxu")
Re: Testing Algorithms (Steven Runyeard)
paper on all 15 AES candidates ?? (Christopher Jobmann)
Re: Standard fileheaders for encrypted files (Kiril Kesarev)
----------------------------------------------------------------------------
From: Anthony Naggs <[EMAIL PROTECTED]>
Subject: Re: VxD Crypto - Win 95/98/NT
Date: Tue, 23 Feb 1999 13:25:10 +0000
After much consideration R H Braddam decided to share these wise words:
>According to the documentation for the Device Drivers
>Development Kit for Win 98/NT, page locking works
>correctly for Virtual Device Drivers (VxD) and device
>drivers (DxD - my own term, if not correct please
>advise).
In Win95 device drivers can be in VxDs or (usually 16-bit) DLLs. Win98
adds WDM (Windows Driver Model) drivers that are more or less compatible
with NT.
'DxD' is not a term anybody else would recognise.
>One of the example VxDs in the DDK is Eatpages.VxD. It
>grabs and locks half of the available pages at boot-up
>and keeps them until shutdown. It is a very simple VxD
>and shows how to allocate, lock, unlock, and deallocate
>memory. The writer suggests that it could be used to
>simulate low memory conditions. It wouldn't work if VxD
>page-locked memory was swappable.
That's what page locked memory is.
>Eatpages.VxD could also serve as a starting point for a
>secure memory allocator for Crypto functions. A VxD can
>map a pointer to its page-locked memory to an
>application's address space. A lot is needed to convert
>it to a memory allocator and manager, though.
You need to be careful, memory in your VxD can be accessed by other VxDs
and even applications. It is not private. Windows 9x is single user
insecure o.s.
>My first inclination is to use two linked lists of
>structures (pointer, size, ...) and two chains of pages
>to allocate from. ...
> ... B-Trees might be better than linked
>lists. They're actually just a special case of a
>doubly-linked list, anyway. Comments?
It rather depends on what you're trying to achieve and your programming
preferences.
Regards.
--
BAD COMPUTER! That's my registry file you've trashed.
------------------------------
From: Alex Vinokur <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,comp.compression,sci.math
Subject: Re: Huffman codes with non-numerical cost?
Date: Tue, 23 Feb 1999 13:09:36 GMT
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
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Date: Tue, 23 Feb 1999 10:34:44 +0100
According to Steven Runyeard <[EMAIL PROTECTED]>:
> >And how much processor power would that be? Have you actually
> >done the math?
>
> Go back 10 years and the best you would have got from an average
> desktop computer was around 10 MIPs. Now we are seeing Pentium
> processors which can almost do 2,000 MIPs.
There's no garantee that this growth rate will continue. In fact
everything points to the opposite.
> Have you done the maths?
>
Yes, several times.
You, on the other hand, *very obviously* have not...
(Ah the joys of Usenet: Open mouth, put foot in it in front of millions)
My maths goes like this:
2^256 is a big number, something like 10^77.
Assuming (let's be generous here) that Intel can make chips a million
times faster than they can today (which they can't - the speed of light
will limit them well before they get to the Teraherz range - but let's
go with it for now...) Let's also assume (optimistically) that Intel
makes them smart enough to test a key in a single clock cycle. If we
assume these two things, a future Pentium might be able to test 2x10^15
keys per second.
Now assume you can afford 100 billion such CPUs (and even if you could,
Intel could never manufacture that many, but let's go with it).
Also asssume that you can buy a small coutry to house them all, and
a few dozen multi-terawatt power stations to run them all. This
(completely inconceivable) setup would let you test a whopping 2x10^26
keys per second.
In one year, you'll be able to test about 32 million times that many
keys, that's about 10^33 keys per year.
My maths says that you've still got a factor of 10^44 to go (that's
44 zeros!) before you can crack a message.
Now, as far as we know, the universe is about 120 billion years old.
Even with these hoplessly optimistic estimates of "increased CPU power",
you'll still need 10^33 times the age of the universe, just to crack
*one* message.
So, that's my maths. Let's see how yours went...
--
<\___/>
/ O O \
\_____/ FTB.
PS: At 2x10^26 keys per second, even a 128 bit key would take longer
than the age of the universe to brute force.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Date: Tue, 23 Feb 1999 10:55:23 +0100
Patrick Juola wrote:
>
> Given that people have, for the past 20 years, routinely been claiming
> that "Moore's Law cannot hold much longer due to fundamental physical
> limitations," it's starting to look like betting that Moore's law
> will NOT hold isn't a safe bet.
>
Simply not true.
For many years people have been saying that Moore's law cannot hold
because of technical difficultiess (eg. the wavelength of light used
to etch the chips). So far, this hasn't come true. Process technologies
have managed to keep up with the "law" (although things are starting
to slow down noticably in the last few years).
Only very recently have people been saying that "Moore's law cannot
hold because of fundamental physical limitations" like the speed of
light. There is no evidence whatsoever that Moore's law can hold
beyond another 15-20 years or so. Electrons/photons simply don't
move that fast...
When this limit is reached, we'll have to move towards more
parallelism in software to get things done (if we actually
need *more* speed on the desktop...)
--
<\___/>
/ O O \
\_____/ FTB.
PS: At 2.5GHz chips will start to emit microwaves - good for keeping
your coffee warm...?
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Interesting DES results
Date: 23 Feb 99 13:31:16 GMT
Paul Rubin ([EMAIL PROTECTED]) wrote:
: In article <[EMAIL PROTECTED]>, bill johnson <same> wrote:
: >The second test was to measure the + or - difference from one byte to
: >the next. This was an eye opener. The plot looks like a nearly perfect
: >inverted 'V'. In fact amazingly so.
: Since the numbers are basically random you'd expect the sum or difference
: to follow a binomial distribution. Not quite an inverted V, but
: might look sort of like one.
Actually, a V is the right shape. We're not talking about a normal
distribution here.
For example, if we take uniformly distributed random numbers from 0 to 6,
and we plot the difference between successive numbers on a scale from -5
to +5, the probabilities are 1/36, 2/36, 3/36 ... 6/36, 5/36 ... 1/36.
In this case, the scale would go from -255 to +255, but the probabilities
would again go up and down linearly.
One die = uniform distribution, two dice = triangular distribution, three
or more dice = approximations to the normal distribution.
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Interesting DES results
Date: 23 Feb 99 13:27:46 GMT
bill johnson ([EMAIL PROTECTED]) wrote:
: The second test was to measure the + or - difference from one byte to
: the next. This was an eye opener. The plot looks like a nearly perfect
: inverted 'V'. In fact amazingly so.
: I've tried this on two different sources and I get the same result.
: Any comments from the grouop? I have the data and source files if
: anyone is interested.
If your source file has duplicate stretches of eight bytes, then, using
ECB, there would be duplicates in the result. Otherwise, it isn't too
surprising that DES produces output with nearly perfect statistical
properties, since it has sixteen rounds, and only four rounds are enough
to thoroughly jumble the input bits.
John Savard
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Testing Algorithms
Date: 23 Feb 1999 08:57:09 -0500
In article <[EMAIL PROTECTED]>,
Safuat Hamdy <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] (Patrick Juola) writes:
>
>> In article <7arsl1$51j$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>> >What is it that drives people to make these wild claims and speculations
>> >without doing the arithmetic? Computers can not continue to get faster
>> >indefinitely.
>>
>> The fact that doomsayers have been predicting physical limits to the
>> maximum speed of computers for 20 years now, and the successive violation
>> of these physical "limits" has become routine.
>
>Bruce Schneier made some interesting estimates in AC about this. Don't have
>the exact numbers in mind, but essentially the message was:
>
>if one bit operation would require one elementary energy unit (this is a
>hard, insurmountable limit)
Except that it isn't. There are lots of (formal) computation methods
around that are (in theory) reversible, and that therefore have no
minimum energy requirement -- you just run the step backwards and you
get all the energy you put into it back out except for parasitic losses
which can be made as small as you like.
Fredkin gates are a good example.
-kitten
------------------------------
From: "Scott Berg" <[EMAIL PROTECTED]>
Subject: Re: Visual Cryptography
Date: Tue, 23 Feb 1999 08:04:06 -0600
It's moved. Try:
http://cacr.math.uwaterloo.ca/~dstinson/visual.html
Jaap-Henk Hoepman wrote in message ...
>alex <[EMAIL PROTECTED]> writes:
>
>>
>> Hi,
>> Anyone can tell me what is visual cryptography? and where do this
>> technique is using? Is it useful? if possible, pls points me to other
>> web-site as I want to know more.
>
>Dear Alex,
>
>Check out D. Stinson's web site at http://bibd.unl.edu/~stinson/
>This should give you nice slides and a paper as a starting point for your
>investigations.
>
>Regards,
>Jaap-Henk
------------------------------
From: "gxu" <[EMAIL PROTECTED]>
Subject: signcode, password
Date: Tue, 23 Feb 1999 09:09:26 -0000
use signcode to sign a .cab file,
it will popup a dialogue box to ask for password.
question:
how to programly get the password like an argument in the command line
statement
thanks!
------------------------------
From: [EMAIL PROTECTED] (Steven Runyeard)
Subject: Re: Testing Algorithms
Date: Tue, 23 Feb 1999 14:21:34 GMT
>So, it is less than an 8-bit longer key advantage... I don't see your
>point.
The point is that there is an improvement. If this trend continues
then ultimately it will be possible to crack and 256 bit key by brute
force in reasonable time.
Steve
------------------------------
From: Christopher Jobmann <[EMAIL PROTECTED]>
Subject: paper on all 15 AES candidates ??
Date: Tue, 23 Feb 1999 15:35:25 +0100
Hello !
I'm looking for a paper (or any other information) giving a brief
overview over all the 15 AES candidates, considering underlying
structure (Feistel-Network, SP-Network and such), Numbers of Rounds, as
well as safety (I heard a couple of the candidates are already broken -
is that true ??).
At the moment I am not interested in speed comparisons that much since I
found the paper from Bruce Schneier (<- and others) and a couple of web
sides addressing that topic.
What I'm looking for is a way to get a basic idea of the 15 algorithms
without going through the whole documentation on the CD1.
Any idea where I could get that ??
thanks in advance, any help is appreciated !
Chris
------------------------------
From: Kiril Kesarev <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Standard fileheaders for encrypted files
Date: Tue, 23 Feb 1999 16:54:49 +0200
[EMAIL PROTECTED] wrote:
> There is no government standard for headers, but the U.S. government does
> individually approve encryption programs for export. And it *does* require
> that encryption programs with 40 or 56 bit keys have mechanisms in place
> to prevent a gain in security from multiple encryption.
So, if a program is granted an export license and that particular program is using
40bit RC4 or key shortened DES, is the software developer really allowed to
call it RC4 or DES if multiple encryption has been prevented? Encryption
algorithms
generally allow any input sequences. Eg. des <some_file_name> will yield an
encrypted file with a magic number preventing multiple encryption. This implies
that when the 'des' is run a second time it will not allow any sequence of bits as
its
input which of course means that the algorithm (program) is not working according
to standards.
BTW, has any software developer (company) been sued for distributing an
encryption program which claims to implement a strong cipher (like Blowfish or
IDEA),
but which has deliberate on accidental weaknesses in the implementation?
Kiril
------------------------------
** 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
******************************
