full-disclosure - DL over GF(p^k), p small

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Date: Mon, 20 Aug 2007 07:22:23 -0700 (PDT)
From: Imaginero Lamero <imaginerolamero@...oo.com>
To: full-disclosure@...ts.grok.org.uk
Subject: DL over GF(p^k), p small

Hello,

Can someone coment on theese fast DLs over GF(p^k) with p smal?

Atached pari programme use p-adic logs, time is less than an minute:

(Numbers may wrap)

(13:19) gp > \r fil.gp 
q=370801^18 ;po1=17 ; po2=3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117109 ; tt=4702816082614016182965692121592448734541768804994600705383687298520660242493249158332154303805784930 ;po1^tt-po2 mod q=0
q=2^2003 ; po1=3 ; po2=19 ; t2=46046993139340166507090345615136250245999852064751171464668824387327204617681975780033079082311475657137920713633763250220430610306299407245801779788107829618296187553498768740217764857679385834036527096610226088132909804871500857727685554848681412848966715381705429730393858144254724754753785416583532641000842142306002349659344124042311390577104136195412245014808630785142511094125656912846715271821518325318857294740147530820821910283761699863431400217626353118504249795670889601044291930122883686330300672097906241079404551995315676104058601306583435730299863940037603350130072634964196048067365501 po1^t2-po2 mod q=0
(13:20)



{
\\ Tries to find l such that
\\ po1^l = po2 mod p^k
\\ Complexity p-1
\\ This program is distributed under the terms of the GPL
dlani(p,k,po1,po2)=
local(i,j,j2,j3,z1,z2,l1,l2,lo,q,kk);
q=p^k;
kk=k+1;
po1=Mod(1,q)*lift(po1);
po2=Mod(1,q)*lift(po2);
z1=polrootspadic(x-lift(po1),p,kk);
z1=z1[1];
z2=polrootspadic(x-lift(po2),p,kk);
z2=z2[1];
l1=log(z1);
l2=log(z2);
lo=lift(Mod(1,p^(k-1))*lift(l2/l1)); \\ ;)
j=po1^lo;
if(j==po2,return(lo));
j3=po1^(p^(k-1));
j2=j3;
for(i=1,p-1,
if((j*j3)==po2,return(lo+i*p^(k-1)));
j3=j3*j2;
);
return(0);
}
p=370801;
k=18;
q=p^k;
ro=znprimroot(q);\\XXX this may be slow
pre=round(log(q)/log(10))-1;
default(realprecision,pre);
sec=floor(Pi()*10^pre)+42;
po1=Mod(ro,q);
po2=sec;
tt=dlani(p,k,po1,po2);
print("q=",p,"^",k," ;po1=",lift(po1)," ; po2=",lift(po2)," ; tt=",tt," ;po1^tt-po2 mod q=",lift(po1^tt-po2));
p=2;
k=2003;
q=p^k;
po1=Mod(3,q);po2=19;\\ 7^2, 13^2
t2=dlani(p,k,po1,po2);
print("q=",p,"^",k," ; po1=",lift(po1)," ; po2=",lift(po2)," ; t2=",t2," po1^t2-po2 mod q=",lift(po1^t2-po2));
2/0; \\ Exit nicely


       
---------------------------------
Choose the right car based on your needs.  Check out Yahoo! Autos new Car Finder tool.
Content of type "text/html" skipped

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/