Stream Cipher

Η ακολουθία αριθμών που παράγει ο Linear Conrguencial Generator

\[ x_{n+1} = a x_n + b \pmod{N}, \]

με \(N = 8699938873, a = 7529942229, b = 4539503045\) και η αρχική τιμή \(x_0\) επιλέγεται τυχαία από το σύνολο \([0,N-1]\), δεν είναι ψευδοτυχαία, όπως δείξατε στην προηγούμενη εργασία. Άρα είναι φυσικό να περιμένει κανείς ότι ο αντίστοιχος stream cipher δεν είναι σημασιολογικά ασφαλής. Δείξτε ότι μπορείτε να κερδίσετε το παιχνίδι της σημασιολογικής ασφάλειας εναντίον του stream cipher που ορίζεται ως εξής: το μήνυμα είναι μία ακολουθία φυσικών αριθμών \(m_0, m_1,\ldots\) με \(0\leq m_i< Ν\), το κλειδί είναι η ακολουθία \(x_0,x_1,\ldots\) με \(0\leq x_i < N\) που παράγει ο παραπάνω LCG και το κρυπτογράφημα είναι το \(c_0, c_1,\ldots\) με \(c_i = (m_i + x_i) \mod N\).

Σε κάθε γραμμή δίνονται δύο μηνύματα \(m_0, m_1\) και το κρυπτογράφημα \(c\) ενός εξ αυτών. Το κλειδί παράγεται πάντα από τον ίδιο LCG, με νέα αρχική τιμή κάθε φορά. Ποιό από τα δύο μηνύματα έχει κρυπτογραφηθεί σε κάθε περίπτωση;

ΜΗΝΥΜΑ 0	ΜΗΝΥΜΑ 1	ΚΡΥΠΤΟΓΡΑΦΗΜΑ
[1096156973, 5118403458, 5862180524]	[3765693374, 5067927110, 840618414561]	[6340593612, 1586239881, 40583217438]
[2561922144, 7595510034, 7962148712]	[4185179295, 3343866988, 507190678497]	[7762959258, 4188785461, 63337970176]
[7477539028, 5348331091, 7948203990]	[5688839965, 162518444, 1325250966]	[4987605644, 4869686599, 79045111344]
[8043453156, 4872079172, 7299962512]	[2058735563, 2465242207, 717818886]	[6574429026, 7724977327, 850993768]
[5740593923, 2146189067, 3275039713]	[2707059090, 1796974115, 66646149428]	[5860174042, 5450826039, 77638817023]
[7869726110, 1576991510, 607446440]	[12869901, 8330949239, 5826747238]	[1926976175, 1702335981, 27249142439]
[8578352288, 3912438252, 8408509640]	[5845953201, 4836470550, 863198680]	[3206693537, 6187732298, 25196655045]
[8370294552, 8135687342, 8526577888]	[3231899097, 7328823180, 367115429934]	[3242249116, 2989015926, 84871007339]
[7280771637, 41862689, 5978822773]	[3711334451, 1281502289, 634756564056]	[5814701877, 8068240649, 44070325793]
[101762633, 5426340179, 4676953514]	[1181932772, 609053945, 5230833378]	[2861655468, 4413759279, 5966268035]