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*shmidA*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*shmidA*M) we get
Mat2*v= (idA, N/M, (idA*shmidA*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
 Truncated multiplication (is it secure???)
 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):
Relevant Pages
