fgrieu
Reputation
33,837
95/100 score
 Dec 14 comment Public key exponent coprime with totient proof $d=e^{-1}\bmod\phi(N)$ is typically not the only working $d$ modulo $\phi(N)$. Counterexample: $N=55$, $\phi(N)=40$, $e=3$, $e^{-1}\bmod\phi(N)=27$. Notwithstanding, $d'=7$ is a perfectly fine private exponent, such that $(a^e)^{d'}\equiv a\pmod N$ for all $a$, even though $e\cdot d'\not\equiv1\pmod{\phi(N)}$. Things are not quite that simple! Dec 13 comment How to compute projective cordinate Z in elliptic curve cryptography? @abejoe: all methods I know for NISTP256 use some number of modular inverse operations with arguments of about 256 bits. The one that I propose uses very few, so that step will not become a bottleneck. And that method is readily understandable if one has already implemented and understood something with affine coordinates and modular inverse at each step. In light of your two other related questions, you seem to be in that situation, and an easy understandable solution might be pedagogical. Dec 13 comment How to compute projective cordinate Z in elliptic curve cryptography? Repeating myself: as an alternative to projective coordinates, you might want to have a look at the simpler technique of using affine coordinates, with all quantities kept as fractions, reducing numerator and denominator modulo $p$ when it gets much larger. Benefits that I expect: the math is easy; and you need to compute modular inverse only twice, when producing the final result; that removes the modular inverse performance bottleneck that you cite in a related question. Dec 13 comment Comparison of Execution time for HMAC MD5 and a multliplication and pairing operations in G, on same CPU One appropriate way is to get working, reasonably optimized code performing each of the two operations you want to compare, at comparable security level, time each (which requires a bit of extra code), and compare. HMAC- MD5 is the easy part. For the other, you will need to define what "pairing operation in G" you want to time, what parameters you need to use for comparable security, and write that code or use a library. Let me Google the later for you. Dec 13 comment Public key exponent coprime with totient proof Are you asking for a proof, rather that an illustration by example as given in the answer to the linked question, of the fact: $$\gcd(e,\varphi(N))\ne1\implies\exists (x,y)\in\mathbb N^2,\;\;x\not\equiv y\pmod N,\;\;x^e\equiv y^e\pmod N$$all other things being as specified in RSA (like, $N$ is a square-free integer, or is it the product of two distinct primes)? Dec 13 comment MiTM on RSA public key encryption @Santiago Gonzalez Toral: I'm afraid that you over-engineered your protocol in a) and that sent you on tracks far from what the problem's author is trying to guide you. What you have been asked in a) [be secure against an adversary assumed not to send any message] can be done simply, with RSA encryption alone. Hint: Alice first sends a non-encrypted message to Bob; after the second message, Bob and Alice have their shared secret key. $\;$ When you use this simple protocol, b) and c) becomes easy. Hint: some of the shared secret can be devoted to protection against MiTM. Dec 12 comment Help with RSA-2048 crypto ransom virus In the short term, restore data files (not programs) from backups to a clean computer (do not bring the backups to the infected one). Or hope the perpetrator made a silly mistake, and someone knowledgeable and with a lot of time will find it, and make a workaround available (that happens for some cryptoransomware). In the long term, understand and master any tool you use; that's valid for computers and milling machines alike. Sorry, this is off-topic. Dec 11 comment Modular Arithmetic in RSA Glad that you got it fixed. The origin of the to the $2/2$ th power evades me, but we can do without it :-) Dec 11 comment Attack on textbook RSA with small messages @poncho: now it is me begging for an extra hint. Would your hint help an elementary attack (simpler than the LLL) for e.g. $e=17$, $\log_2(N)\approx 1024$, random 80-bit $m$ ? Dec 10 comment Is there any alternative for extended euclidean algorithm to perform modulo division? I assume you are working modulo some prime $p$. While your 90% is a lot, and perhaps could be reduced somewhat, what you describe is to be expected. Indeed, that overhead can be avoided. A simple and instructive method is to work with quantities kept as a fraction of two integers, without modular inversion. Usual algebraic rules for fractions apply unchanged for modular fractions. Both numerator and denominator should be reduced modulo $p$, at least regularly in the ongoing computation or/and when their absolute value exceeds some threshold. It does not pay to further reduce the fraction. Dec 10 comment How to perfrom modular division while numerator is lesser than the denominator? @abejoe: Yes, in elliptic curves using $\mathbb Z_p$ as the base group, while computing slope, the numerator reduced modulo $p$ is often smaller than the denominator reduced modulo $p$. As explained in the answer, there is no need whatsoever to consider if this is the case, or not; and there are alternative definitions of smaller. $\;$ I have recently been reminded that comments are not for chat, and I don't chat, so that will be the end of it. Dec 10 comment How to perfrom modular division while numerator is lesser than the denominator? @abejoe: notice that $140/14\pmod{101}$ [written $140/14\pmod{101}$ ] is not, strictly speaking, an integer; that's the class of integers $x$ such that $14x-140$ is a multiple of $101$. On the other hand, $140/14\bmod 101$ [written $140/14\bmod{101}$ or $140/14\bmod101$ ] is the non-negative integer less than $101$ with this property, that is $10$. Dec 10 comment How to perfrom modular division while numerator is lesser than the denominator? @abejoe: $140/14\bmod101$ is indeed $10$. That's also true if you change $101$ to any integer at least $11$. The method you are using, and that I describe, does work. The coincidence with the result over the integers is because 14 happens to divide 140. $\;$ My explanation is in layman's terms, except for "a representative integer of the residue class of the equivalence relation modulo $p$", which you can skip and replace with the alternative that I give following "that is". Just take care of reading my text carefully, and grasping the definition of "reducing modulo $p$". Dec 9 comment Is there a fast implementation of RSA for Microcontrollers? The paper's claim is $76⋅10^6$ CPU cycles for 1024-bit private key operation (+12% for side-channel protection), with like $\mathcal O(n^3)$ scaling. This is impressive, but still credible: about 8 cycles for one 8×8→16 bit MUL and two 8-bit ADD, which leave about 4 cycles for operand fetches and overhead, using a method that plausibly minimizes fetches and overhead by leveraging the numerous CPU registers. However, in practical terms in the Smart Card industry that still is too slow, not security certified. We do private-key RSA with special hardware; software is good only for public-key. Dec 8 comment RSA message integrity @lel: protocol analysis is hard even with a full description of the protocol, and the only firm conclusions that can be made with a partial description is that the protocol is insecure; thus without a full description, you'll only get conclusions of this kind. And, with the re-use assumption, I do not even get how the extended protocol resists better against any of the three bulleted attacks; thus I pass at further analysis. Dec 8 comment RSA message integrity We are asked a question about a part of the protocol, with the rest unspecified; in that situation, I find it prudent to assume the worse. $\;$ I agree, of course, with your remark that concatenation is unsafe in the context. Dec 8 comment Modular Arithmetic in RSA $\gcd(187^2-1,1457)=1457$, and $\gcd(187^2+1,1457)=1$. Dec 8 comment Largest number that could be factored in milli seconds I second that SQUFOF is to consider; it think I remember that it has been used with success in the sieving phase of some optimized MPQS/GNFS factorization code, at least by Robert D. Silverman (aka Pubkeybreaker). Dec 8 comment Largest number that could be factored in milli seconds @sashank: following mikeazo's remark, you might want to change the question on the line of: What would be the largest bound such that any lower integer could be factored into its prime factors in millseconds (or perhap: most lower integer) Dec 7 comment Largest number that could be factored in milli seconds Is the use of GNFS central to the question? If yes, an answer will be hard, for existing GNFS implementations are optimized for factorization efforts requiring 6 to 9 decimal order of magnitude more work than what you consider. Also, it seems more interesting in practice to ask the question prescribing the timeframe, but not the algorithm. Algorithms other than GNFS could well be faster (at least in practice) for numbers factorisable within these constraints. Argument: in GNFS as practiced, a significant portion of the time is spent factoring many auxiliary composites, with other algorithms.