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

*From*: "daniel bleichenbacher" <daniel_bleichenbacher@xxxxxxxxx>*Date*: 23 Mar 2007 12:32:11 -0700

On Mar 22, 9:47 pm, "Bill" <wherr...@xxxxxxxxxxxxxxxx> wrote:

This gives the matrix

| 1 0 0 |

| 0 N/M 0 |

| sh*N/M^2 -midA*N/M N^2/M^2 |

Now (idA, N/M, (idA*sh-midA*M)*N/M^2) is a linear combination of the

column vectors of this matrix.

I followed you til here, and then you lost me... Would you please

mind showing me the matrix used to transform the matrix that way? I

mean there should be a way to add or multiply the rows of the original

matrix to get that row, right?

Let Mat1 be

|1 0 0|

|0 1 0|

|sh -midA*M N|

and Mat2 be

|1 0 0|

|0 N/M 0|

|0 0 N/M^2|

then computing Mat2*Mat1 gives

| 1 0 0 |

| 0 N/M 0 |

| sh*N/M^2 -midA*N/M N^2/M^2 |

A vector v is a linear combination of columns of Mat1 if there exists

a column vector w such that

v = Mat1*w. This implies that Mat2*Mat1*w = Mat2*v is a linear

combination of Mat2*Mat1.

For the column vector v= (idA , 1, idA*sh-midA*M) we get

Mat2*v= (idA, N/M, (idA*sh-midA*M)*N/M^2).

Also, here is a Pari script that I used to solve the example given

earlier.

\\ Implementation of integer mod operation

\\ (It proabably already exists, but I couldn't find this function.)

imod(m,n) = m - floor(m/n)*n

\\ Example from sci.crypt

sh = 31356540235810673346618362866804034368776251178676;

idA = 4466022725645872080780142446;

idB = 3223756751453228576175422353;

M = 10^11;

N = 10^67;

\\ Computation of MidA and MidB

MidA = floor(imod(sh*idA,N)/M);

MidB = floor(imod(sh*idB,N)/M);

print("MidA = ", MidA);

print("MidB = ", MidB);

print("");

\\ Given MidA solve for idA

mat = [1,0,0; 0,1,0; sh, -MidA*M, N];

mul = matdiagonal([1, N/M, N/(M^2)]);

t = qflll(mul*mat,1);

red = mat*t;

print("Reduced basis for idA", red);

print("");

\\ Given MidB solve for idB

mat = [1,0,0; 0,1,0; sh, -MidB*M, N];

mul = matdiagonal([1, N/M, N/(M^2)]);

t = qflll(mul*mat,1);

red = mat*t;

print("Reduced basis for idB", red);

print("");

.

**References**:**Truncated multiplication (is it secure???)***From:*Kiuhnm

**Re: Truncated multiplication (is it secure???)***From:*Phil Carmody

**Re: Truncated multiplication (is it secure???)***From:*daniel bleichenbacher

**Re: Truncated multiplication (is it secure???)***From:*daniel bleichenbacher

**Re: Truncated multiplication (is it secure???)***From:*Bill

- Prev by Date:
**Re: World is complicated** - Next by Date:
**Re: Beginner Question:Rijndael encrypted value over SSL** - Previous by thread:
**Re: Truncated multiplication (is it secure???)** - Next by thread:
**Re: Truncated multiplication (is it secure???)** - Index(es):