import randomP = 295075153L # about 2^28class WeakPrng(object): def __init__(self, p): # generate seed with 56 bits of entropy self.p = p self.x = random.randint(0, p) self.y = random.randint(0, p) def next(self): # x_{i+1} = 2*x_{i}+5 (mod p) self.x = (2*self.x + 5) % self.p # y_{i+1} = 3*y_{i}+7 (mod p) self.y = (3*self.y + 7) % self.p # z_{i+1} = x_{i+1} xor y_{i+1} return (self.x ^ self.y) prng = WeakPrng(P)for i in range(1, 10): print "output #%d: %d" % (i, prng.next())
x_{i+1} = 2*x_{i}+5
crypto-class Це щось типу латексового запису математичного виразу Xi+1 = Xi * 2 + 5.Підказка: ця штука вирішується брутфорсом, але чого - не скажу. Зверніть увагу, як між собою пов’язані x, y та z (кінцеве значення).
crypto-class Підказка: ця штука вирішується брутфорсом, але чого - не скажу. Зверніть увагу, як між собою пов’язані x, y та z (кінцеве значення).
#include <iostream>#include <sstream>using namespace std;typedef unsigned long ulong;int main() { const ulong P = 295075153; ulong x, y; const int kO = 9; ulong o[kO+1] = {210205973, 22795300, 58776750, 121262470, 264731963, 140842553, 242590528, 195244728, 86752752, 0}; for(x = 0; x <= P; x++) { y = o[0] ^ x; ulong right = y; ulong left = x; stringstream s; for (int j = 0; j < kO+1; j++) { right = (3 * right + 7) % P; left = (2 * left + 5) % P; if ((right ^ left) != o[j+1]) { if (j) cout << s.str() << j << ": " << (right ^ left) << endl; break; } else { s << j << ": " << (right ^ left) << endl; } } }}
231886864
Підкажіть, будь ласка, розв"язок першої задачки. А то в мене вийшов рядок, але він його не приймає, може я просто якийсь місспелінг роблю.
Цитата: Yola від 2012-04-05 11:25:29231886864Красивий код, я за нестачею часу зупинився на "волохатому" рішенні (на C).ЦитатаПідкажіть, будь ласка, розв"язок першої задачки. А то в мене вийшов рядок, але він його не приймає, може я просто якийсь місспелінг роблю.spoilermy @guesses = ("We can factor the number 15 with quantum computers. We can also factor the number 15 with a dog trained to bark three times - Robert Harley","Euler would probably enjoy that now his theorem becomes a corner stone of crypto - Annonymous on Euler's theorem","The nice thing about Keeyloq is now we cryptographers can drive a lot of fancy cars - Dan Boneh","The ciphertext produced by a weak encryption algorithm looks as good as ciphertext produced by a strong encryption algorithm - Philip Zimmermann","You don't want to buy a set of car keys from a guy who specializes in stealing cars - Marc Rotenberg commenting on Clipper","There are two types of cryptography - that which will keep secrets safe from your little sister, and that which will keep secrets safe from your government - "There are two types of cyptography: one that allows the Government to use brute force to break the code, and one that requires the Government to use brute for"We can see the point where the chip is unhappy if a wrong bit is sent and consumes more power from the environment - Adi Shamir","A (private-key) encryption scheme states 3 algorithms, namely a procedure for generating keys, a procedure for encrypting, and a procedure for decrypting. "," The Concise OxfordDictionary (2006) def ines crypto as the art of writing o r solving codes. ","The secret message is: When using a stream cipher, never use the key more than once",);
#include <gmp.h>#include <gmpxx.h> #include <iostream>#include <iomanip>#include <map>#include <ctime>using namespace std;#include "eu.h"const long k2in20 = 1048576;const mpz_class g("11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568");const mpz_class p("13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171");const mpz_class h("3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333");//const long k2in20 = 8;//const mpz_class g("57");//const mpz_class p("137");//const mpz_class h("8");inline void percentage(string prefix, long l) { if (!(l % 1000)) cout << prefix << setprecision(3) << setw(5) << setfill(' ') << (double)l / 1000 / 10 << "%" << endl;}int main() { time_t started_at = time(0); cout << "Start time is " << ctime(&started_at) << endl; map<mpz_class, long> left; mpz_class g_accum = 1; mpz_class gcd, x, y; for (long l = 1; l <= k2in20; l++) { g_accum *= g; g_accum %= p; ex_al_eu(g_accum, p, gcd, x, y); mpz_class key = (x * h) % p + ((x * h) % p < 0 ? p : 0); left[key] = l; percentage("Left: ", l);// cout << "left[" << key << "] = " << l << endl; } mpz_powm_ui(g_accum.get_mpz_t(), g.get_mpz_t(), k2in20, p.get_mpz_t()); mpz_class g_accum2 = 1; for (long l = 1; l <= k2in20; l++) { g_accum2 *= g_accum; g_accum2 %= p;// cout << g_accum2 << endl; if (left.find(g_accum2) != left.end()) { cout << "Answer is x1 = " << left[g_accum2] << " and x0 = " << l << endl; break; } percentage("Right: ", l); } time_t ended_at = time(0); cout << "End time is " << ctime(&ended_at) << endl; cout << "Execution time is " << ended_at - started_at << endl; return 0;}
template<class T> void ex_al_eu_in(const T &r1, const T &r2, const T &x1, const T &x2, const T &y1, const T &y2, T &gcd, T &a, T &b) { T r3 = r1 - r2 * (r1 / r2); T x3 = x1 - x2 * (r1 / r2); T y3 = y1 - y2 * (r1 / r2); if (0 != r3) ex_al_eu_in(r2, r3, x2, x3, y2, y3, gcd, a, b); else { gcd = r2; a = x2; b = y2; }}template<class T> void ex_al_eu(const T &r1, const T &r2, T &gcd, T &a, T &b) { if (0 == r1 || 0 == r2) gcd = a = b = 0; else ex_al_eu_in(r1 > r2 ? r1 : r2, r1 < r2 ? r1 : r2, T(1), T(0), T(0), T(1), gcd, r1 > r2 ? a : b, r1 < r2 ? a : b);}
./configure --enable-cxx make make installmake check
