Cryptography-Digest Digest #458, Volume #14 Sun, 27 May 01 16:13:01 EDT
Contents:
Re: Euroean commision will recommend all citizens to use encryption in (Mok-Kong
Shen)
A problem of combinatronics; Square-1 ("BenZen")
A problem of combinatronic$ :: ATTN: Mr Mok Kong Shen ("BenZen")
Re: Euroean commision will recommend all citizens to use encryption in email next
week, because of echelon. (SCOTT19U.ZIP_GUY)
Re: Medical data confidentiality on network comms (Tom McCune)
Re: good x86 coders (help please) (Jerry Coffin)
Re: good x86 coders (help please) ("Tom St Denis")
A problem of combinatronics: Sphere-1 ("BenZen")
Re: To prove PGP can easily be misused... (wtshaw)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Euroean commision will recommend all citizens to use encryption in
Date: Sun, 27 May 2001 19:33:29 +0200
Jan Panteltje wrote:
[snip]
> It seems Echelon is used by the US and GB for industrial espionage,
> I suppose they (the commision) thinks that by everyone encrypting their
> email Echelon will become rather useles.
There may well be other systems than Echelon. If everyone
encrypts (no matter whether important matters or trivial
stuffs and use a plethora of algorithms -- some even quite
poor 'security by obscurity' unknown home-made ones for
the trivial stuffs just to confuse the opponents, since
he has in each case first to identify the algorithms used),
then such systems would certainly be bogged down due to
enormous overload. But the hardest problem is to mobilize
the public to use encryptions everywhere everytime.
[snip]
> I cannot stand for the accuracty of this news report, especially as I think
> encryption is not allowed in France, and GB is a member of the EEC.
> So it may be a hoax.
France had a very restictive crypto law. But that has
been discarded (presumably due to the Echelon affairs), or
am I ill-informed in that?
M. K. Shen
------------------------------
From: "BenZen" <[EMAIL PROTECTED]>
Subject: A problem of combinatronics; Square-1
Date: Sun, 27 May 2001 13:59:34 -0400
Dear Cryptologist and neophytes.
Some of you might own a toy, Square-1 cube.
Looking like a Rubic cube, at first but having odd geometry.
A few years ago I bought such an amusing toy and soon found-out
I had no rules to solve it once it was shuffled.
So I decided to write a program that would give me the path
back to shape. I failed, but had a good time programming this
on a 486, back then. Now I just found this page:
http://www.org2.com/jaap/puzzles/square1.htm
This clever Jaap Scherphuis programmer seems to have nailed it;
Using an algorithm similar in design to the Kociemba for Rubik.
Since the center layer is made-up of only two shapes; It allows only
180deg rotation; Allowing each TOP or Down sides to gather a
variable number of elements, between 6 and 10. Each one being
of a unique color sheme making them all different.
One Mathematical question I can't figure-out is the shape of the
configuration tree it would make, if one could draw branches from
each state into the other allowed ones.
(Not counting 90deg center flip, from which there are no alternative
other than flipping back 90deg on way or the other.)
I had a strange idea it would be some sort of conical shape, from
the single center FLIP requirement; Then; Depending on the
current TOP/Bottom geometry, a variable number of Flip is possible
from all combinations or matching the "center-split plane" through
simple rotation of TOP/Bottom.. Center plane being mainly a two-state
element, distinguishing odd and even flips.
I had the feeling this Square-1 allowed state graph, would look like
some sort of a baloon, where you pinch each extremities and pull
them together hoping for a donut.
Wondering how the state nodes inside link to each other;
Wondering about the actual pattern of the branches.
Is it very thick; mostly linear but extremely long as opposed to
very thick and with branches of various lenghts.
The simple study of this cube proved to me much more fascinating,
than just playing with it.
With my recent readings on crypto, I can even imagine the Square-1
algorithm be re-used to generate an interesting cypher.
If the tree is not too thick. ;)
What do you think,
Regards,
Ben
------------------------------
From: "BenZen" <[EMAIL PROTECTED]>
Subject: A problem of combinatronic$ :: ATTN: Mr Mok Kong Shen
Date: Sun, 27 May 2001 14:01:11 -0400
Dear Cryptologists and neophytes.
I recently stumbled on Mr Mok Kong Shen's WWW page
and found two interesting cryptology related problems,
with a potential reward.
http://home.t-online.de/home/mok-kong.shen/
After someone kindly translated the combinatronics question
into Layman's language; I could make more sense of it and
the challenge seemed appealing so I already wrote a
program with some of my neophyte ideas about it.
Then I wondered about the 200$ reward.
What are the exact criterias, aside the fact Mr Shen expects the applicants
to be 'experts' as he states in the first parragraph ?
Then I noticed the date on this page:
Publication date: 14th Nov. 1997. Last revised: 3rd August 1999.
Certainly he must have received some satisfactory solutions since then ?
Then why does he still want to distribute this 200$ reward; Or is he very rich ?
I hope this is not a covered way to gather 'fresh ideas' for free while the reward
could never be really granted. Oh I know some University professors who are
constantly giving their little problems to students. One of them even started
a company with a idea from a fiend of mine; rewritten under his name.
But I am pretty confident this is not the case.
So I wonder, how many applicants have already received the reward ?
Could Mr Kong be kind enough to comment on the interesting ideas
he already received.
Or maybe some of you in this group already had the pleasure of wining the reward ?
Regards,
Neophyte cryptologist... Therefore I don't quality.
Ben
======== My 2 cent wort of combinatronics ===========
About my preliminary one night study on this particular problem, I attach my
own neophyte findings, from yesterday's work. This puzzle is amusing indeed.
======
HAMMING DISTANCE
A measure of the difference between two messages,
each consisting of a finite string of characterS,
expressed by the number of characters that need to be changed
to obtain one from the other. E.g., 0101 and 0110 has a Hamming distance
of two whereas "Butter" and "ladder" are four characters apart
(see error detecting code, error correcting code). (Krippendorff)
=======
=======
LATIN SQUARE background:
Latin squares are also linked to algebraic objects known as quasigroups.
A quasigroup is defined in terms of a set, Q, of distinct symbols and
a binary operation (called multiplication) involving only the elements of Q.
A quasigroup's multiplication table turns out to be a Latin square.
Each element of the set Q occurs exactly once in each row and each column
of the table.
Computer scientists have proved that the quasigroup completion problem
belongs to a category of difficult computational problems described as
NP-complete. As the number of elements, n, increases,
a computer’s solution time grows exponentially in the worst case.
A good link on this can be found here:
http://www.vsv.slu.se/johnb/java/latin2.htm
Basic program to create Latin Squares from random seed.
10 CLS : DEFINT A-Z: COLOR 15: PRINT "ANY POSSIBLE LATIN SQUARE"
20 COLOR 11: INPUT "ENTER NUMBER OF TREATMENTS"; N
30 INPUT "ENTER NUMBER FOR RANDOM SEED"; RN: RN = RND(-RN)
40 COLOR 15: DIM C(N): DIM A(N, N)
50 FOR R = 1 TO N
60 FOR C = 1 TO N: C(C) = C: NEXT C: J = N
70 FOR C = 1 TO N: I = 0
80 X = INT(RND * J + 1)
90 REM CHECK COLUMN IF OK (ROW IS INHERENTLY OK)
100 FOR H = 1 TO R - 1
110 IF I > 50 THEN 60: REM ROW NO GOOD
120 IF A(H, C) = C(X) THEN I = I + 1: GOTO 80: REM COLUMN NO GOOD
130 NEXT H
140 A(R, C) = C(X): J = J - 1
150 FOR K = X TO J: C(K) = C(K + 1): NEXT K: NEXT C
160 FOR CL = 1 TO N: PRINT USING "###"; A(R, CL); : NEXT: PRINT : NEXT
=======
Now Back to Shen's problem:
http://home.t-online.de/home/mok-kong.shen/#problem1
For arbitrary given m determine g(m) := max { n | H(m,n) > 0 }.
With the help of John; I could figure-out the question.
--- John Layman's language. ---
g(m) is the largest multiple of m for which there exists an m by g(m)
matrix of which the each group of m columns are an m by m Latin
square, so that within each of these squares, no two columns have the
same number in any row, and any two columns from two different squares
have exactly one number matching.
Defining H(m,n) as the number of _distinct_ such matrices, when we are
really looking for the largest n for which any such matrix exists, is
somewhat of a confusing smokescreen.
================================
--- Okay.. In Benzman's language now. ---
What Bubba wants is; For an arbitrary m the largest set of
Shen's squares(*) for which the following restrictions apply:
*) -A Shen's square is a variant of Latin Square with column 1
always be (1, 2, ..... m). 'm' being the size of a column.
-Also, Shen's sqares have a special property on any pairs of
its (m) columns. The total difference between elements of these
columns must be (m) also.
1) The superset of Shen's squares must be of a dimension: (m x n);
n being a multiple of m.
2) Between any pairs of columns within the whole set (n)
The total difference between elements of these columns must
be (m-1) also.
3) No two Shen's squares within must be considered equivalent.
Equivalence being defined as transformed to one other by
simple permutation of columns.
=======================================
So we want the largest Bubba said !
Let's rewrite the sample basic algorithm in C language,
in which I can Zen it better. Boy it's gonna be a fun rainy saturday night ;)
Thanks bubba... I always wanted to work on N-complex proggies but my boss
would not let me.
Since I'm new to this, I'm gonna proceed in steps.
1) Write a simple C version of the random Latin square generator.
2) Add Shen's rules to generate a version 1, limited (m) size Shen square. ;)
3) Determine a better algorithm.
4) Get the money and give it to Tom St-Denis for summer break. ;)
A few minute reading the BASIC Latin square program sufficed
to make me sick; It's completely unstructured with goto's out
of loops; And dependent on a random trials and errors.
Impossible to predict computational time. == Trash.
Seems that I must write my own amusing version.
I studied a little to understand the Latin Square Theory better:
FACT 1: Marriage Theorem. (Taken from the web)
"Latin squares of order n are extremely numerous for n>3.
Indeed, the first row can be any one of n! permutations.
After the first row is chosen, there are approximately n!/e choices
for the second row (e is the base for the natural logarithm).
And, no matter how many rows are chosen less than n rows consistent
with being a latin square, it is always possible to choose another row.
So any consistent start with k rows can always be completed to
a latin square. This fact is based on a fundamental theorem in combinatorics
variously known as the Marriage Theorem and the theorem on
distinct representatives."
Playing with my own program, I found another interesting FACT.
FACT#2
We can Always build a Latin Square, from a ((i+j)modulo size)+1;
Where i,j are row,column indexes starting at 0.
IDEA:
>From that starting square, I might build a program that can
then find the permutations to all other squares. When I can
establish the proper construction rules.
Indeed, this initial square fits Shen's criterias for column 1.
IDEA: From the symetry I could find four at a time.
Yet, the restriction for the first column prevents this on
the first submatrix.
IDEA: The non-equivalence criterias forbids to use row shuffling.
Only horizontal flips could be useful later.
IDEA: I noticed that in order to have Hamming value of m-1 between
submatrix, one item per column MUST be identical,
in each sub-matrix; since each column must have distinct value.
Then any of the rows between any sub matrix MUST have
exactly one match. This is a strong requirement that will greatly
limit the number of such sub-matrix, I call Shen squares.
(*) Then It's always possible to duplicate one row from submatrix 1,
onto the other ones.
A very efficient rudimentary formula like S(i,j) =((i+j)modulo size)+1,
can be adapted to this idea, by simple remapping of S(i,j) through a
vectored (indirection) matrix T. Matrix T1 is a array of permutable
pointers into a final result matrix S2; S, being the original Shen matrix
derived from ((i+j) mod m)+1;
Q:.. Instead of the obvious (duplicating an entire row onto each matrixes);
Is it possible to target just any row element S(Ki,j) ;Where Ki is an
element of a column hold array Ch(i) = [K1,K2...m].
ex: Fixing row1 for m=4; Ch = [1,1,1,1]; Then determine the proper
Transformation matrix T1 from it from a simple algorithm.
IDEA: I wonder if after a sufficient study, I can generalize the technique and
without even generating these Shen sub-matrix; determine the exact
number of allowed permutations for each; Thus giving rise to a simple
equation: F(m,n) = number of possible sub-matrix, for any m. By first
finding a rule that computes the greatest n, multiple of m.
IDEA: I shall eventually find-out it's a N-complex problem, but right now
the restrictions with Hamming of (m-1) on the sub-matrix seems
to be key limiting factor.
Other ideas are being tested in my preliminary BenShen Square program.
This was my two cents worth; Wishing good luck to the neophytes like myself.
===========================================================
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Euroean commision will recommend all citizens to use encryption in email
next week, because of echelon.
Date: 27 May 2001 17:55:28 GMT
[EMAIL PROTECTED] (John Savard) wrote in
<[EMAIL PROTECTED]>:
>On Sun, 27 May 2001 13:22:56 GMT, [EMAIL PROTECTED] (Jan
>Panteltje) wrote, in part:
>
>>It seems Echelon is used by the US and GB for industrial espionage,
>>I suppose they (the commision) thinks that by everyone encrypting their
>>email Echelon will become rather useles.
>
>And yet there was a recent news item that said Holland was planning to
>follow the same path as Britain with its R.I.P. bill.
Thats because must politicans are crooks so they expect
evryone else to be crooked. Once in power they want to do
everything possible to stay in power. All govenments if not
carefully watched end up destroying themeselves and freedom.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
Crossposted-To: comp.security.misc
From: Tom McCune <[EMAIL PROTECTED]>
Subject: Re: Medical data confidentiality on network comms
Date: Sun, 27 May 2001 18:13:38 GMT
In article <9eju29$156j$[EMAIL PROTECTED]>, "Harris Georgiou" <[EMAIL PROTECTED]>
wrote:
>The term "closed loop" I used refers to a group of processes (services)
>working together independently or in sequence (request relay), so my design
>mainly addresses the issue of authenticated processes interconnection rather
>than physical login by users.
>Anyway, is it a fact that biometric security devices have been used in
>medical facilities? I thought only military or goverment organizations could
>affort the cost of them :-o
>Cheers!
I work for the a State Office of Mental Health.
Our facility policy does not allow the transfer of any patient information
over the internet, but state OMH policy requires that patient information
transferred over the internet be encrypted (that was not clarified in the
policy when I looked - probably a year or so ago).
We have a state wide area network that we can transfer patient
information over - I beieve that is encrypted - transparently to the user,
so I have no idea what that consists of.
If my recall is correct, HCFA requires 128 bit symmetric encryption (but I
almost get the idea that it might have said something about either 112 or
168 bit, which would be in reference to Triple DES, I assume - that was
again some time ago when I looked that up). What I was then surprised about
was that the asymmetric encryption was only required to be 1024 bit - I
would have thought longer term privacy would warrant 2048 bits.
I am now required to do my psychological evaluations, progress notes,
etc., while connected to a server in the state capitol (about 80 miles
away), and that requires fingerprint scan verification.
Tom McCune
http://www.McCune.cc
Please use PGP for Privacy & Authenticity
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: good x86 coders (help please)
Date: Sun, 27 May 2001 12:43:52 -0600
In article <3B00FB77.3DD689B6
@evidian.earth.sun.milkyway.universe.com.invalid>,
[EMAIL PROTECTED]
says...
[ ... ]
> Unfortunately I dont currently have an assembler that supports the MMX
> instructions.
If you're using assembly on a regular basis, there's no reason to put
up with this. MASM is available for free as part of the DDK on the
MS web site. That gets you version 6.11; you'll want to upgrade to
version 6.14, which is available as a patch named ml614.exe on the
MSDN web site (msdn.microsoft.com).
If you prefer a different assembler, NASM (available from various
places) handles MMX as well. I don't particularly like its syntax
and it's definitely quite a bit slower than MASM, but is is a
competent assembler nonetheless and handles essentially all
instructions on any x86 variant out there.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: good x86 coders (help please)
Date: Sun, 27 May 2001 19:41:06 GMT
"Jerry Coffin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <3B00FB77.3DD689B6
> @evidian.earth.sun.milkyway.universe.com.invalid>,
> [EMAIL PROTECTED]
> says...
> [ ... ]
>
> > Unfortunately I dont currently have an assembler that supports the MMX
> > instructions.
>
> If you're using assembly on a regular basis, there's no reason to put
> up with this. MASM is available for free as part of the DDK on the
> MS web site. That gets you version 6.11; you'll want to upgrade to
> version 6.14, which is available as a patch named ml614.exe on the
> MSDN web site (msdn.microsoft.com).
>
> If you prefer a different assembler, NASM (available from various
> places) handles MMX as well. I don't particularly like its syntax
> and it's definitely quite a bit slower than MASM, but is is a
> competent assembler nonetheless and handles essentially all
> instructions on any x86 variant out there.
I would argue there are more reasons to use NASM over MASM. First off it's
much simpler syntax makes for easy coding (no stupid DWORD PTR, or kooky
declarations). All of NASM syntax is fairly logical. NASM (0.98) supports
macros, equates, multiple segments, etc..
Also NASM is portable, you can make a 16-bit build or 32-bit build just as
easy. I have NASM installed in RH Linux and in Windows.
Finally NASM also can output to about 10 diff object file formats.
Simply put NASM is an x86 assembler done right.
Nuff ranting...this is afterall OT for this group.
Tom
------------------------------
From: "BenZen" <[EMAIL PROTECTED]>
Subject: A problem of combinatronics: Sphere-1
Date: Sun, 27 May 2001 15:47:55 -0400
To explain the idea of a tree of states with branches
going from one state to another allowed one in a
single allowed manipulation, I introduce the
Sphere-1 toy.
It's in the shape of a shpere, being sliced through the
center of symetry into various prism of identical
shapes and sizes, except for their color being all different.
This toy fits in the hand but nothing holds the pieces together,
Like a Square-1 or Rubik cube.
The rules to 'flip' such a sphere is even simpler.
To go from holding one spherical configuration to another,
you are allowed to drop it and put it back in any order you like.
LOL... A flat pie would be more practical indeed.
Such a toy, modelize a tree or configurations which nodes can be linked
to any other with a branch. For a 'n' facet sphere, the number
of possible configuration is just plain, (n-1)!/2 . I think,
I'm no Math specialist.
*) How can one classify various 'tree' topologies emerging, from different
geometrical restrictions, in regard to 3D objects that are holding
together and allowed to be transtated only through rotation 'flip',
of their joing flat surfaces; Or with moveable parts such as this sphere.
*) IMHO, this tree is representing some sort of fractal dimention.
'Fractals and scale', by David G.Green; In my words:
"A Line is considered to have a dimension of 1, surfaces 2
and solids a dimension of 3. However a rough curve, in the extreme
may effectively fill the surface on which it lies. Same logic applies
to extremely convoluted surfaces onto 3D. Then the 'roughness' can
be thought as increasing the dimension of the object. For convoluted
Lines This expression is:
log (L2 / L1)
D= ----------------- , Where L1,2 measures the lengths in units of the curves,
log(S1 / S2) And S1,2 are the sizes of the units (scales).
Sampling an actual curved line with two different unit lengts, or increasing
Precision, we can have for example the set1(L=1,S=7) set2 finer(L=0.5,S=20)
Therefore estimate a Fractal dimension of log(20/7)/(log(2) = 1.51
Considering my graph problem, I wonder how we could translate a
tree of configuration, into L and S parameters that would express
the complexity (Fractal dimension) of the graph.
I believe this fractal dimension for such graphs could be even greater than
3 dimension, for the Spherical example I just gave; Since all the nodes
are linked to all the other nodes, rendering impossible a 3D representation
without having branches crossing each others.
If I am right; Then is there a Limit to the dimension and how can it be
calculated.
I can't explain properly how this translate into Fractal encryption yet.
Crasy ideas from a neophyte,
Food for thought,
Regards,
Benoit. AKA: Ben Zen
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: To prove PGP can easily be misused...
Date: Sun, 27 May 2001 13:42:41 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> >
> > Hmm might not be news to you, but think about this. What if some
> > politician happened about this and decided to trust it without
> > confirmation? Ouch... bad news...
>
> High-ranking politicians are supposed to have people
> knowledgeable in security working for them to take care
> of the privacy of their communications.
>
> M. K. Shen
It does not follow that they are in place or even have competence to pick
qualified people. The military point of view is to threaten and
intimidate to get what they want, which extends to the way certain
organizations try to push their own agendas, those of politicians be
damned. Privacy is their last consideration if that cannot also be
subverted. Security is not an art but a science to be learned at all
levels; leave it to someone else and your surrender your privacy.
--
Suppose California quit sending food back East.
Would Gerorge be ready to barter with energy?
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************