The impossible chessboard puzzle

https://www.youtube.com/watch?v=wTJI_WuZSwE [www.youtube.com]

2021-03-25 22:55

Bit strings, error correcting, and coloring the corners of higher dimensional cubes.

tag: math

The impossible chessboard puzzle

https://www.youtube.com/watch?v=wTJI_WuZSwE [www.youtube.com]

2021-03-25 22:55

Bit strings, error correcting, and coloring the corners of higher dimensional cubes.

Recovering A Full Pem Private Key When Half Of It Is Redacted

https://blog.cryptohack.org/twitter-secrets [blog.cryptohack.org]

2021-03-25 02:26

The @CryptoHack__ account was pinged today by ENOENT, with a CTF-like challenge found in the wild: Source tweet. Here’s a write-up covering how given a partially redacted PEM, the whole private key can be recovered. The Twitter user, SAXX, shared a partially redacted private RSA key in a tweet about a penetration test where they had recovered a private key. Precisely, a screenshot of a PEM was shared online with 31 of 51 total lines of the file redacted. As ENOENT correctly identified, the redaction they had offered wasn’t sufficient, and from the shared screenshot, it was possible to totally recover the private key.

source: L

What are the most important statistical ideas of the past 50 years?

http://www.stat.columbia.edu/~gelman/research/unpublished/stat50.pdf [www.stat.columbia.edu]

2021-03-12 03:30

We argue that the most important statistical ideas of the past half century are: counterfactual causal inference, bootstrapping and simulation-based inference, overparameterized models and regularization, multilevel models, generic computation algorithms, adaptive decision analysis, robust inference, and exploratory data analysis. We discuss common features of these ideas, how they relate to modern computing and big data, and how they might be developed and extended in future decades. The goal of this article is to provoke thought and discussion regarding the larger themes of research in statistics and data science.

source: danluu

donut.c without a math library

https://www.a1k0n.net/2021/01/13/optimizing-donut.html [www.a1k0n.net]

2021-01-20 05:39

My little donut.c has been making the rounds again, after being featured in a couple YouTube videos (e.g., Lex Fridman and Joma Tech). If I had known how much attention this code would get over the years, I would have spent more time on it.

Re-Deriving the edwards25519 Decoding Formulas

https://buttondown.email/cryptography-dispatches/archive/cryptography-dispatches-re-deriving-the/ [buttondown.email]

2020-12-21 17:03

A lot of my job is implementing specifications, and sometimes in a crypto spec you’ll encounter something like this and what you do is nod, copy it into a comment, break it down into a sequence of operations, and check that the result matches a test case. However, the other day I was having a bit of an identity crisis because I could not remember basic algebra, so I went and re-derived the edwards25519 point decoding formulas as a sort of homework. It turned out to be pretty useful for understanding pieces of the implementation I had been just treating as black boxes. I’m going to try to take you along for the ride, to show that there is no dark magic involved, and that we can all get to the same result as the specification with step-by-step high-school algebra.

Floating-Point Formats

http://www.quadibloc.com/comp/cp0201.htm [www.quadibloc.com]

2020-12-13 07:05

Part of Computer Arithmetic. http://www.quadibloc.com/comp/cp02.htm

And How does a computer work? http://www.quadibloc.com/comp/cpint.htm

source: trivium

Baby Sharks - Injecting small order points to threshold EdDSA

https://medium.com/zengo/baby-sharks-a3b9ceb4efe0 [medium.com]

2020-12-11 07:03

We showcase one example of how an attacker can inject a low order subgroup group element in threshold EdDSA protocol secure against malicious adversaries, bypassing existing protections.

source: green

Dissecting Lemire’s nearly divisionless random

https://veryseriousblog.com/posts/dissecting-lemire [veryseriousblog.com]

2020-10-03 03:40

The idea was simple, I’ve always felt that code readability is undervalued so I figured I’d put cold hard cash up. I announced a $1,000 pot, divided into $500, $300, and $200 prizes for the most readable implementations of Daniel Lemire’s nearly divisionless algorithm for selecting a random number from an interval. I now have winners to announce and congratulate, and they’re in this blog post, but there’s more to this story.

This equation will change how you see the world (the logistic map)

https://www.youtube.com/watch?v=ovJcsL7vyrk [www.youtube.com]

2020-08-17 04:46

That may be over selling it, but cool anyway.

Is X25519 Associative? Sometimes!

https://buttondown.email/cryptography-dispatches/archive/cryptography-dispatches-is-x25519-associative/ [buttondown.email]

2020-05-28 04:40

The age design includes a double invocation of X25519: once with a domain separation tweak, once with the actual secret. While implementing this I wondered: can we multiply those two scalars first, instead of doing two point multiplications in a row? It would be much faster!

Extracting ROM constants from the 8087 math coprocessor's die

http://www.righto.com/2020/05/extracting-rom-constants-from-8087-math.html [www.righto.com]

2020-05-17 23:20

I opened up an 8087 chip and took photos with a microscope. The photo below shows the chip’s tiny silicon die. Around the edges of the chip, tiny bond wires connect the chip to the 40 external pins. The labels show the main functional blocks, based on my reverse engineering. By examining the chip closely, various constants can be read out of the chip’s ROM, numbers such as pi that the chip uses in its calculations.

Byrne’s Euclid

https://www.c82.net/euclid/ [www.c82.net]

2020-04-27 04:08

If one of the lines paſs through the centre, it is evident that it cannot be biſected by the other, which does not paſs through the centre.

I probably could have done without ye olde spelling, but nice web conversion otherwise.

Ten Lessons I Wish I Had Learned Before I Started Teaching Differential Equations

https://web.williams.edu/Mathematics/lg5/Rota.pdf [web.williams.edu]

2020-04-20 21:57

One of many mistakes of my youth was writing a textbook in ordinary differential equations. It set me back several years in my career in mathematics. However, it had a redeeming feature: it led me to realize that I had no idea what a differential equation is. The more I teach differential equations, the less I understand the mystery of differential equations.

source: trivium

Forecasting s-curves is hard

https://constancecrozier.com/2020/04/16/forecasting-s-curves-is-hard/ [constancecrozier.com]

2020-04-19 14:30

S-curves have only three parameters, and so it is perhaps impressive that they fit a variety of systems so well. Broadly, the three parameters describe the initial growth rate, the level-off rate, and the value at which it levels-off. Therefore, if you can estimate these three numbers, then you have the trend curve. Many of us will have learnt in school that if there are three parameters to be found, you need three data points to define the function. This would suggest that you could perfectly predict the level-off point based on only three observations (spoiler: you can’t).

source: HN

Another look at two Linux KASLR patches

https://www.kryptoslogic.com/blog/2020/03/another-look-at-two-linux-kaslr-patches/ [www.kryptoslogic.com]

2020-03-25 01:51

In the end, this random number generator was quickly removed, and that was that. But one can still wonder—is this generator secure but unanalyzed, or would it have been broken just to prove a point?

source: R

Landmark Computer Science Proof Cascades Through Physics and Math

https://www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/ [www.quantamagazine.org]

2020-03-08 04:00

Computer scientists established a new boundary on computationally verifiable knowledge. In doing so, they solved major open problems in quantum mechanics and pure mathematics.

source: green

Building Lattice Reduction (LLL) Intuition

https://kel.bz/post/lll/ [kel.bz]

2020-01-24 07:49

The Lenstra–Lenstra–Lovász (LLL) algorithm is an algorithm that efficiently transforms a “bad” basis for a lattice L into a “pretty good” basis for the same lattice. This transformation of a bad basis into a better basis is known as lattice reduction, and it has useful applications. For example, there is attack against ECDSA implementations that leverage biased RNGs that can lead to private key recovery. However, my experience learning why LLL works has been pretty rough. Most material covering LLL seems targeted towards mathematicians and I had to (I guess I wanted to) spend a lot of time trying to weasel out the intuition and mechanics of the algorithm. This blog post is a semi-organized brain dump of that process. My goal is to cover LLL in such a way that slowly ratchets down the hand-waving, so feel free to read until you are happy with your level of understanding.

The Hidden Number Problem

https://github.com/kelbyludwig/notebooks/blob/master/The%20Hidden%20Number%20Problem.ipynb [github.com]

2020-01-24 07:47

The Hidden Number Problem (HNP) is a problem that poses the question: Are the most signficant bits of a Diffie-Hellman shared key as hard to compute as the entire secret? The original problem was defined in the paper “Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes” by Dan Boneh and Ramarathnam Venkatesan.

In this paper Boneh and Venkatesan demonstrate that a bounded number of most signifcant bits of a shared secret are as hard to compute as the entire secret itself. They also demonstrate an efficient algorithm for recovering secrets given a significant enough bit leakage. This notebook walks through some of the paper and demonstrates some of the results.

Big Data+Small Bias

http://marginalrevolution.com/marginalrevolution/2020/01/big-datasmall-bias.html [marginalrevolution.com]

2020-01-15 18:20

Among experts it’s well understood that “big data” doesn’t solve problems of bias. But how much should one trust an estimate from a big but possibly biased data set compared to a much smaller random sample? In Statistical paradises and paradoxes in big data, Xiao-Li Meng provides some answers which are shocking, even to experts.

source: MR

Isogeny crypto

https://ellipticnews.wordpress.com/2019/11/09/isogeny-crypto/ [ellipticnews.wordpress.com]

2019-11-11 05:24

Rolling forward 15 years, isogeny-based cryptography is another area with many technical subtleties, but is moving into the mainstream of cryptography. Once again, not everything that can be done with discrete logarithms can necessarily be done with isogenies. It is therefore not surprising to find papers that have issues with their security.

It is probably time for an Isogenies for Cryptographers paper, but I don’t have time to write it. Instead, in this blog post I will mention several recent examples of incorrect papers. My hope is that these examples are instructional and will help prevent future mistakes. My intention is not to bring shame upon the authors.

source: green