forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 19 Νοέμ 2017, 03:01

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 1 δημοσίευση ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Ασκηση κρυπτογραφίας στο Mathematica
ΔημοσίευσηΔημοσιεύτηκε: 12 Μάιος 2014, 16:34 
Χωρίς σύνδεση
Άβαταρ μέλους

Εγγραφη: 25 Ιουν 2011, 11:22
Δημοσ.: 17
Έχει κανείς ιδέα πως λύνεται αυτή η άσκηση στο mathematica;

5. Index calculus for DLP in F^*_p

----------
Exercise 5
In this exercise you should use index calculus to solve the following DLP:
g^x=h (mod p)
where
p=486130339139
g=1301
h=56499970361


The following simple function computes random powers g^i (mod p) and returns the first it finds that is B-smooth, where B is the b:th prime number.

GuessSmoothPowers=Function[{g,p,b},
Module[{res,Lp,st,i,gi,git,j,gie,Lgie},
Lp=Map[Prime,Range[b]];st=0;
While[st==0,
i=RandomInteger[{2,p-2}];gi=PowerMod[g,i,p];
git=gi;Lgie={};For[j=0,j<Length[Lp],j++,gie=IntegerExponent[git,Lp[[j+1]]];Lgie=Append[Lgie,gie];git=git/Lp[[j+1]]^gie];If[git==1,st=1;res={Lgie,i}]
];
res
]]

Try, for example:
R1=GuessSmoothPowers[2,853,4]

When I did this the outcome was:
{{3,2,1,0},90}
which means that 2^90=2^3*3^2*5^1*7^0 mod 853.

To take the r:th element of a list R then type R[[r]]. Try for example:
R1[[1]]

If A is a matrix and b a vector then
LinearSolve[A,b,Modulus->p]
computes one solution to the equation A*x=b mod p.
Try, for example:
LinearSolve[{{1,2},{1,3}},{4,7},Modulus->11]
where the matrix A has rows {1,2} and {1,3}.


If r={r1,...,rk} and m={m1,...,mk} then
ChineseRemainder[r,m]
computes the solution to the set of equations x=ri mod mi for i=1,..,k.
Try, for example:
ChineseRemainder[{3,7},{7,11}]

Finally, the following function computes the smallest k such that h*g^(-k) (mod p) is B-smooth, where B is the b:th prime number.

Smoothen=Function[{g,h,p,b},
Module[{Lp,st,gh,k,ght,Lghe,j,ghe},
Lp=Map[Prime,Range[b]];st=0;gh=h;
For[k=0,k<p&st==0,ght=gh;Lghe={};For[j=0,j<Length[Lp],j++,ghe=IntegerExponent[ght,Lp[[j+1]]];Lghe=Append[Lghe,ghe];ght=ght/Lp[[j+1]]^ghe];If[ght==1,st=1,gh=Mod[gh*PowerMod[g,-1,p],p];k++]];
Print["k=",k];FactorInteger[gh]]]

(a) What is the theoretically suggested value for B that should make the hunt with GuessSmoothPowers the most efficient? Time how long it takes to find a "smooth power" for this value of B.

(b) Solve the DLP using index calculus. (You might want to use a smaller B than the theoretical one suggested in (a) to decrease the number of times you need to use the function GuessSmoothPowers.)


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 1 δημοσίευση ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group