Prev: Updating the Historic OTP.
Next: CFP DATA MINING 2010: new date - until 29 March 2010
From: Pubkeybreaker on 23 Mar 2010 17:52
On Mar 23, 3:53�pm, Martin Lauridsen <martinlaurid...(a)gmail.com>
wrote:
> On 23 Mar., 18:27, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
>
>
>
>
>
> > What is "this"? �Are you asking why B^2- 4AC is 0 or 1 mod 4?
> > Or are you asking why it must equal k*N �(not just N) for some
> > selected multiplier �k?
>
> > If the former, observe that all squares are either 0 or 1 mod 4 �[do
> > you see why?]
> > and that 4AC is 0 mod 4.
>
> > We are trying to find polynomials �f(x) �such that g^2(x) = �f(x) �= a
> > mod N
> > and also that �p divides f(x), �f(x+p), �f(x+2p) .... � for certain
> > primes p � (primes in the factor base)
> > Now solve �f(x) = 0 mod p � using the quadratic formula mod p and use
> > the fact that p is
> > a quad. residue of kN. �If the discriminant is not a square mod N,
> > then the polynomial will not
> > generate squares mod N.
>
> Hi Pubkeybreaker.
>
> I see that any square must be 0 or 1 (mod 4), since we have four
> cases:
>
> a = 0 (mod 4) => a^2 = 0 (mod 4)
> a = 1 (mod 4) => a^2 = 1 (mod 4)
> a = 2 (mod 4) => a^2 = 4 = 1 (mod 4)
> a = 3 (mod 4) => a^2 = 9 = 1 (mod 4)
>
> Yes, I understand that we must find some polynomial, lets call it
> Q(x), which generates squares (mod N).
> I have already implemented this, for the single polynomial case. Here
> I use Q(x) = (x + m)^2 - N, � where m = floor(sqrt(N)).
>
> We want Q(x) to produce a lot of values, that are smooth with regard
> to the factor base, for a somewhat small interval [-M, M].
> I am in doubt how to choose the coeffecients A, B and C in Q(x) = Ax^2
> + Bx + C, to obtain this.- Hide quoted text -
>
> - Show quoted text -

It is all discussed in the Math. Comp. paper
From: Scott Contini on 23 Mar 2010 20:42
On Mar 24, 6:53 am, Martin Lauridsen <martinlaurid...(a)gmail.com>
wrote:
> On 23 Mar., 18:27, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
>
>
>
> > What is "this"?  Are you asking why B^2- 4AC is 0 or 1 mod 4?
> > Or are you asking why it must equal k*N  (not just N) for some
> > selected multiplier  k?
>
> > If the former, observe that all squares are either 0 or 1 mod 4  [do
> > you see why?]
> > and that 4AC is 0 mod 4.
>
> > We are trying to find polynomials  f(x)  such that g^2(x) =  f(x)  = a
> > mod N
> > and also that  p divides f(x),  f(x+p),  f(x+2p) ....   for certain
> > primes p   (primes in the factor base)
> > Now solve  f(x) = 0 mod p   using the quadratic formula mod p and use
> > the fact that p is
> > a quad. residue of kN.  If the discriminant is not a square mod N,
> > then the polynomial will not
> > generate squares mod N.
>
> Hi Pubkeybreaker.
>
> I see that any square must be 0 or 1 (mod 4), since we have four
> cases:
>
> a = 0 (mod 4) => a^2 = 0 (mod 4)
> a = 1 (mod 4) => a^2 = 1 (mod 4)
> a = 2 (mod 4) => a^2 = 4 = 1 (mod 4)
> a = 3 (mod 4) => a^2 = 9 = 1 (mod 4)
>
> Yes, I understand that we must find some polynomial, lets call it
> Q(x), which generates squares (mod N).
> I have already implemented this, for the single polynomial case. Here
> I use Q(x) = (x + m)^2 - N,   where m = floor(sqrt(N)).
>
> We want Q(x) to produce a lot of values, that are smooth with regard
> to the factor base, for a somewhat small interval [-M, M].
> I am in doubt how to choose the coeffecients A, B and C in Q(x) = Ax^2
> + Bx + C, to obtain this.

I also learned it from Bob's paper, but if you want a second
explanation, see:
http://www.crypto-world.com/documents/contini_siqs.pdf
It's summarised compactly in Figure 2.2, and the logic behind it
is explained in section 2 pages 6 - 9.

Scott
From: adacrypt on 24 Mar 2010 07:57
On Mar 23, 7:53 pm, Martin Lauridsen <martinlaurid...(a)gmail.com>
wrote:
> On 23 Mar., 18:27, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
>
>
>
>
>
> > What is "this"?  Are you asking why B^2- 4AC is 0 or 1 mod 4?
> > Or are you asking why it must equal k*N  (not just N) for some
> > selected multiplier  k?
>
> > If the former, observe that all squares are either 0 or 1 mod 4  [do
> > you see why?]
> > and that 4AC is 0 mod 4.
>
> > We are trying to find polynomials  f(x)  such that g^2(x) =  f(x)  = a
> > mod N
> > and also that  p divides f(x),  f(x+p),  f(x+2p) ....   for certain
> > primes p   (primes in the factor base)
> > Now solve  f(x) = 0 mod p   using the quadratic formula mod p and use
> > the fact that p is
> > a quad. residue of kN.  If the discriminant is not a square mod N,
> > then the polynomial will not
> > generate squares mod N.
>
> Hi Pubkeybreaker.
>
> I see that any square must be 0 or 1 (mod 4), since we have four
> cases:
>
> a = 0 (mod 4) => a^2 = 0 (mod 4)
> a = 1 (mod 4) => a^2 = 1 (mod 4)
> a = 2 (mod 4) => a^2 = 4 = 1 (mod 4)
> a = 3 (mod 4) => a^2 = 9 = 1 (mod 4)
>
> Yes, I understand that we must find some polynomial, lets call it
> Q(x), which generates squares (mod N).
> I have already implemented this, for the single polynomial case. Here
> I use Q(x) = (x + m)^2 - N,   where m = floor(sqrt(N)).
>
> We want Q(x) to produce a lot of values, that are smooth with regard
> to the factor base, for a somewhat small interval [-M, M].
> I am in doubt how to choose the coeffecients A, B and C in Q(x) = Ax^2
> + Bx + C, to obtain this.- Hide quoted text -
>
> - Show quoted text -

Hi Martin,
This is exactly the kind of discussion that I am promoting in my
poster below. Your discussion prompts me a follows. I will dive in
quickly with the outline of what might be another very elegant
adaptation of the Vigenere cipher. This is only a suggestion but it
is worth researching. I am tempted to keep it to myself but that
would be plagiarism - some thing I despise !

(Plaintext + Key) Mod N = Ciphertext (In general)
Put (Plaintext + Key) = a residue
(then, put ciphertext = residue - N). - this step is simply to give
more (invertible) entanglement for confusion.

The domain of both the plaintext and the Key is the set of positive
integers 32 to 126 which you will recognise as the decimal
representation of the writable subset of ASCII. These values are
invertible by means of the language attributes of any of the
programming languages which is why I suggest they should be used for
the obvious convenience that it provides in writing efficient program
sourcecode.

In order for a quadratic equation to have real roots (B^2 - 4AC) >= 0

*Put the Plaintext for encryption as one root and put 'Key' as the
other root. Use any N as a chosen parameter to get a residue.

Then,

Random Key set: The scrambled set of ASCII integers is one random key
(This can be 'sliced' also i.e. the start point for reading is
continually changing in practise for extra entanglement)

N is a key also albeit a single constant parameter for the duration of
a session.

The Ciphertext is collected in a stream cipher and comprises the
encrypted message.

The arrays of keys comprise the mutual database that Alice (alone)
controls by periodically sending fresh scrambling parameters to Bob
that he must apply to stay in sync with her.

The adversary has an equation in three unknowns to solve for a
successful cryptanalysis.

No apologies for any glaring oversight - it is coming off the top of
my head rather quickly - worth testing I think. - adacrypt
From: adacrypt on 24 Mar 2010 08:30
On Mar 24, 11:57 am, adacrypt <austin.oby...(a)hotmail.com> wrote:
> On Mar 23, 7:53 pm, Martin Lauridsen <martinlaurid...(a)gmail.com>
> wrote:
>
>
>
>
>
> > On 23 Mar., 18:27, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
>
> > > What is "this"?  Are you asking why B^2- 4AC is 0 or 1 mod 4?
> > > Or are you asking why it must equal k*N  (not just N) for some
> > > selected multiplier  k?
>
> > > If the former, observe that all squares are either 0 or 1 mod 4  [do
> > > you see why?]
> > > and that 4AC is 0 mod 4.
>
> > > We are trying to find polynomials  f(x)  such that g^2(x) =  f(x)  = a
> > > mod N
> > > and also that  p divides f(x),  f(x+p),  f(x+2p) ....   for certain
> > > primes p   (primes in the factor base)
> > > Now solve  f(x) = 0 mod p   using the quadratic formula mod p and use
> > > the fact that p is
> > > a quad. residue of kN.  If the discriminant is not a square mod N,
> > > then the polynomial will not
> > > generate squares mod N.
>
> > Hi Pubkeybreaker.
>
> > I see that any square must be 0 or 1 (mod 4), since we have four
> > cases:
>
> > a = 0 (mod 4) => a^2 = 0 (mod 4)
> > a = 1 (mod 4) => a^2 = 1 (mod 4)
> > a = 2 (mod 4) => a^2 = 4 = 1 (mod 4)
> > a = 3 (mod 4) => a^2 = 9 = 1 (mod 4)
>
> > Yes, I understand that we must find some polynomial, lets call it
> > Q(x), which generates squares (mod N).
> > I have already implemented this, for the single polynomial case. Here
> > I use Q(x) = (x + m)^2 - N,   where m = floor(sqrt(N)).
>
> > We want Q(x) to produce a lot of values, that are smooth with regard
> > to the factor base, for a somewhat small interval [-M, M].
> > I am in doubt how to choose the coeffecients A, B and C in Q(x) = Ax^2
> > + Bx + C, to obtain this.- Hide quoted text -
>
> > - Show quoted text -
>
> Hi Martin,
> This is exactly the kind of discussion that I am promoting in my
> poster below.  Your discussion prompts me a follows.  I will dive in
> quickly with the outline of what might be another very elegant
> adaptation of the Vigenere cipher.  This is only a suggestion but it
> is worth researching.  I am tempted to keep it to myself but that
> would be plagiarism - some thing I despise !
>
> (Plaintext + Key) Mod N = Ciphertext (In general)
> Put (Plaintext + Key) = a residue
> (then, put ciphertext = residue - N). - this step is simply to give
> more (invertible) entanglement for confusion.
>
> The domain of both the plaintext and the Key is the set of positive
> integers 32 to 126 which you will recognise as the decimal
> representation of the writable subset of ASCII.  These values are
> invertible by means of the language attributes of any of the
> programming languages which is why I suggest they should be used for
> the obvious convenience that it provides in writing efficient program
> sourcecode.
>
> In order for a quadratic equation to have real roots (B^2 - 4AC) >= 0
>
> *Put the Plaintext for encryption as one root and put 'Key' as the
> other root.  Use any N  as a chosen parameter to get a residue.
>
> Then,
>
> Random Key set: The scrambled set of ASCII integers is one random key
> (This can be 'sliced' also i.e. the start point for reading is
> continually changing in practise for extra entanglement)
>
> N is a key also albeit a single constant parameter for the duration of
> a session.
>
> The Ciphertext is collected in a stream cipher and comprises the
> encrypted message.
>
> The arrays of keys comprise the mutual database that Alice (alone)
> controls by periodically sending fresh scrambling parameters to Bob
> that he must apply to stay in sync with her.
>
> The adversary has an equation in three unknowns to solve for a
> successful cryptanalysis.
>
> No apologies for any glaring oversight - it is coming off the top of
> my head rather quickly - worth testing I think. - adacrypt- Hide quoted text -
>
> - Show quoted text -

First refinement,

Instead of treating the modulus N as a constant positive integer make
it a variable element of a larger set of positive integers that are
read sequentially from an array in sync with how the plaintext and key
elements are read in at encryption time.

The range of the set should be 252<= N <= A large positive integer
number greater than any expected message length (say)'

The random key (must equal message length) is a round multiple of the
95 keys in one base set of ASCII - e.g 770 character message requires
95 x 9 = 855 key length ( <= 855 -770 = 85 padding places) and so on -
adacrypt
From: Tom St Denis on 24 Mar 2010 08:34
On Mar 24, 7:57 am, adacrypt <austin.oby...(a)hotmail.com> wrote:
> On Mar 23, 7:53 pm, Martin Lauridsen <martinlaurid...(a)gmail.com>
> wrote:
>
>
>
>
>
> > On 23 Mar., 18:27, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
>
> > > What is "this"?  Are you asking why B^2- 4AC is 0 or 1 mod 4?
> > > Or are you asking why it must equal k*N  (not just N) for some
> > > selected multiplier  k?
>
> > > If the former, observe that all squares are either 0 or 1 mod 4  [do
> > > you see why?]
> > > and that 4AC is 0 mod 4.
>
> > > We are trying to find polynomials  f(x)  such that g^2(x) =  f(x)  = a
> > > mod N
> > > and also that  p divides f(x),  f(x+p),  f(x+2p) ....   for certain
> > > primes p   (primes in the factor base)
> > > Now solve  f(x) = 0 mod p   using the quadratic formula mod p and use
> > > the fact that p is
> > > a quad. residue of kN.  If the discriminant is not a square mod N,
> > > then the polynomial will not
> > > generate squares mod N.
>
> > Hi Pubkeybreaker.
>
> > I see that any square must be 0 or 1 (mod 4), since we have four
> > cases:
>
> > a = 0 (mod 4) => a^2 = 0 (mod 4)
> > a = 1 (mod 4) => a^2 = 1 (mod 4)
> > a = 2 (mod 4) => a^2 = 4 = 1 (mod 4)
> > a = 3 (mod 4) => a^2 = 9 = 1 (mod 4)
>
> > Yes, I understand that we must find some polynomial, lets call it
> > Q(x), which generates squares (mod N).
> > I have already implemented this, for the single polynomial case. Here
> > I use Q(x) = (x + m)^2 - N,   where m = floor(sqrt(N)).
>
> > We want Q(x) to produce a lot of values, that are smooth with regard
> > to the factor base, for a somewhat small interval [-M, M].
> > I am in doubt how to choose the coeffecients A, B and C in Q(x) = Ax^2
> > + Bx + C, to obtain this.- Hide quoted text -
>
> > - Show quoted text -
>
> Hi Martin,
> This is exactly the kind of discussion that I am promoting in my
> poster below.  Your discussion prompts me a follows.  I will dive in
> quickly with the outline of what might be another very elegant
> adaptation of the Vigenere cipher.  This is only a suggestion but it
> is worth researching.  I am tempted to keep it to myself but that
> would be plagiarism - some thing I despise !

<snip>

I love how despite the fact he has no idea what he's talking about or
what the QS is, he decides to inject himself in the conversation.
Awesome.

Tom
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Updating the Historic OTP.
Next: CFP DATA MINING 2010: new date - until 29 March 2010