Re: Truncated multiplication (is it secure???)

Kiuhnm <"kiuhnm03["@]yahoo.it> writes:
A (brand new, I think) company named Xor Labs has proposed a very
simple cryptographic system called XEVRON.
The method is very simple.

1) Alice and Bob choose a common value Sh.
2) Alice generates a private random number idA.
3) Bob generates a private random number idB.
4) Alice computes idA*Sh and removes the n least significant digits
(LSD) and the n most significant digits (MSD) from it obtaining
midA. Alice sends the truncated value to Bob.
5) Bob computes idB*Sh and removes the n LSD and the n MSD from it
obtaining midB. Bob sends the truncated value to Alice.
6) Alice computes SecA = midB*idA.
7) Bob computes SecB = midA*idB.

The middle parts of SecA and SecB are (or should be) identical,
therefore, Bob and Alice have successfully exchanged a secret sequence
of digits.

For instance,

Sh = 31356540235810673346618362866804034368776251178676 (public)
idA = 4466022725645872080780142446 (Alice's)
idB = 3223756751453228576175422353 (Bob's)
midA = Trunc(Sh*idA, n=11) =
07596398517187085436866841011511082698521273905990903873 (public)
midB = Trunc(Sh*idB, n=11) =
74094702438805240690212977889295113208465707248692447576 (public)

SecA = midB*idA =
330908624941672826410522480259254687282490036289143524193970577756316934433667410896
SecB = midA*idB =
24488941006511161091119055359254687282490036289143524195846203343459100001998473169
^^^^^^^^^^
Common subsequence = 9254687282

(We can, of course, use bigger numbers.)

Let <x> be the truncated version of x and x ~ y mean that x and y have
a common central subsequence.
Basically, this method is based on the fact that <idA*Sh>*idB ~
idA*<Sh*idB>.

I think it can be cracked with lattice reduction.
What do you think?

Unfortunately, the documentation of XEVRON is written in Italian, but
an English version should be made available soon
(http://www.xorlabs.net/).


I couldn't get GP's LLL to reverse that particular example, but I'm
no expert at driving it.

I keep thinking that continued fraction convergents might also point
to a solution - have you considered that at all?

Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.
.

Relevant Pages

  • Re: Truncated multiplication (is it secure???)
    ... Alice generates a private random number idA. ... Bob generates a private random number idB. ...
    (sci.crypt)
  • Re: Is this a hoax or real?
    ... Alice is the bad guy. ... location of a file that Bob, the good guy, can get to. ... Alice has her own Web server. ... Alice can pilfer more than a file. ...
    (microsoft.public.security)
  • Is this a hoax or real?
    ... Coan's free Hidden File Detector software. ... Alice is the bad guy. ... location of a file that Bob, the good guy, can get to. ... Alice has her own Web server. ...
    (microsoft.public.security)
  • Whats the problem
    ... Alice is the bad guy. ... location of a file that Bob, the good guy, can get to. ... Alice has her own Web server. ... Alice can pilfer more than a file. ...
    (microsoft.public.security)
  • Does Microsoft listen or care?
    ... Alice is the bad guy. ... location of a file that Bob, the good guy, can get to. ... Alice has her own Web server. ... Alice can pilfer more than a file. ...
    (microsoft.public.win2000.security)