Posts Tagged ‘cryptography’
“Things that are so far removed from our daily experience… are inherently hard to understand”*…
That’s certainly true of numbers. And as the numbers grow, the cognitive challenges grow with them. (Indeed, by way of example: 1 million seconds, is roughly 11.5 days; 1 billion seconds is almost 32 years.)
We’ve looked before at the mysterious extremes of math: zero and infinity [and here]. But as Dan Falk reminds us, the numbers in between can seem pretty strange as well– especially the extremely large ones. In a review of Richard Elwes‘ Huge Numbers: A Story of Counting Ambitiously, From 4½ to Fish 7, Falk spotlights some of the largest numbers humans have ever contemplated…
… Aficionados of huge numbers are called “googologists,” a reference to the number 10100, known as a googol. Such numbers have a peculiar sort of existence. For the vast majority of us, they’re of limited everyday value. Calculations at the supermarket checkout, or at tax time in April, typically involve far more modest figures. Perhaps we’ve read that the U.S. national debt is in excess of $38 trillion — a mind-numbing figure, to be sure, but it’s not as though any one individual needs to count it up in stacks of $20 bills.
And yet, much larger numbers await those who seek them out. Consider the kinds of numbers that crop up in problems involving combinations and permutations. For example, in how many distinct ways can one shuffle a deck of cards? Elwes takes us through the calculation, and we end up with a figure of about 8×1067. Compared to that number, the odds of getting a royal flush when dealt a five-card poker hand seem pretty decent, sitting at a mere 1 in 649,740 (still rare enough that many poker players have never held such a hand). Or consider that famous 1980s cultural touchstone, the Rubik’s cube. In how many ways can one scramble the cube? It turns out that the figure is about 43 quintillion, or 4.3×1019 — but in spite of that ridiculously large figure, people do routinely solve the puzzle, and champions can do it in mere seconds. In fact, as Elwes explains, no Rubik’s cube arrangement is more than 20 moves away from any other arrangement.
Or consider the age of the universe, estimated to be about 13.8 billion years. This may seem like a lengthy span of time, but our cosmic future is where the really big numbers come up. Elwes examines the so-called heat death of the universe, in which all matter has broken down into subatomic particles. We may reach this point in [10 raised to the 10th power, raised again to the 120th power] years — this dizzying figure is 10 raised to the power of 10120 — at which point, Elwes says, the universe will have ballooned up to a diameter of 10 to the power of 10 to the power of 10120 light years. (Yes, that’s [10 raised to the 10th power, again to the 10th power, then to the 120th power] light years.) Elwes adds a footnote: “At this point, the choice of units hardly matters; the distance is so immense that whether we choose to measure it in Planck lengths or giga-light years makes little difference.” Let that sink in!
As mind numbing as such figures are, the highest numbers contemplated by humans come not from physics but from pure mathematics and computer science. Like “Graham’s number” — an immense figure put forward as the upper-bound for solutions to a problem in a branch of mathematics known as Ramsey theory. Some readers may find the ensuing discussion of multi-dimensional hypercubes a bit challenging, but one can enjoy the payoff regardless: We end up with a number that can’t even be expressed in conventional notation, and which earned a mention in the 1980 edition of the “Guinness Book of World Records” as “the highest number ever used in a mathematical proof.”
Reading this book is a little bit like sitting in the back row of an auction house where a rare Picasso (let’s say) is up for grabs: How high is this thing going to go? And indeed, Elwes keeps going. We eventually meet the so-called busy beaver numbers, a set of numbers that crop up in theoretical computer science, when one tries to deduce whether a particular computer program will eventually stop, or keep going forever — a conundrum known as the “halting problem.” As Elwes explains, it’s not at all straightforward to distinguish the two types of programs (and if it was, it would help mathematicians tackle some of the most vexing problems in their field).
The fifth busy beaver number, known as BB(5) — associated with a computer program that can access five internal states — works out to 47,176,870. And that’s as far as we’ve gotten, Elwes explains. No one has worked out the value of BB(6), but he assures us that it’s beyond the range of any physical computer; and BB(16) leaves even Graham’s number in the dust.
But wait, there’s more! “Rayo’s number,” concocted by Agustín Rayo — a dean and professor at MIT — using set theory, is bigger still (here’s a fun video about it); and “Fish 7,” mentioned in the book’s subtitle, named for a Japanese googologist who goes by the pseudonym “Fish,” builds on Rayo’s number, and … well, the details are not easily digested, but the mind-melting nature of these numbers comes across as a feature, not a bug, of Elwes’s story… the narrative is enlivened by explorations of the peculiarities of math history…
… Archimedes tried to estimate how many grains of sand would be needed to fill up the known universe, back in the third century B.C. Did he simply have too much time on his hands? Not at all, insists Elwes: The Greek thinker was articulating an important idea — that no matter how unfathomably large a quantity may be, we can describe it with precision, thanks to mathematics. “Archimedes,” he writes, “was penning a manifesto for the expressive power of large numbers.”…
… [Elwes focuses] on numbers that are ridiculously large and yet finite. In the end, perhaps this is the most mind-boggling fact of all: that these enormous numbers, from Graham’s number to Fish 7 and beyond, fall as far short of infinity as does the humble number 1…
The mysteries of the massive: “The Mind-Boggling Science of Enormous Numbers,” @danfalk.bsky.social on @richardelwes.bsky.social in @undark.org.
###
As we enumerate enormity, we might spare a thought for a seminal mathematician, Alan Turing; he died on this date in 1954. He was a foundational computer science pioneer (inventor of the Turing Machine (an influential model for the general-purpose computer), creator of the “Turing Test” (only too relevant in these AI-infected times), inspiration for “The Turing Award” (the “Nobel Prize of computing“), and cryptographer (leading member of the team that cracked the Enigma code during WWII).
“If geometry is dressed in a suit coat, topology dons jeans and a T-shirt”*…
Paulina Rowińska on how, in the mid-19th century, Bernhard Riemann conceived of a new way to think about mathematical spaces, providing the foundation for modern geometry and physics…
Standing in the middle of a field, we can easily forget that we live on a round planet. We’re so small in comparison to the Earth that from our point of view, it looks flat.
The world is full of such shapes — ones that look flat to an ant living on them, even though they might have a more complicated global structure. Mathematicians call these shapes manifolds. Introduced by Bernhard Riemann in the mid-19th century, manifolds transformed how mathematicians think about space. It was no longer just a physical setting for other mathematical objects, but rather an abstract, well-defined object worth studying in its own right.
This new perspective allowed mathematicians to rigorously explore higher-dimensional spaces — leading to the birth of modern topology, a field dedicated to the study of mathematical spaces like manifolds. Manifolds have also come to occupy a central role in fields such as geometry, dynamical systems, data analysis and physics.
Today, they give mathematicians a common vocabulary for solving all sorts of problems. They’re as fundamental to mathematics as the alphabet is to language. “If I know Cyrillic, do I know Russian?” said Fabrizio Bianchi, a mathematician at the University of Pisa in Italy. “No. But try to learn Russian without learning Cyrillic.”
So what are manifolds, and what kind of vocabulary do they provide?…
[Rowińska explains manifolds and the history of the development of our understanding of them, concentrating on the pivotal role of Riemann…]
… Manifolds are crucial to our understanding of the universe… In his general theory of relativity, Einstein described space-time as a four-dimensional manifold, and gravity as that manifold’s curvature. And the three-dimensional space we see around us is also a manifold — one that, as manifolds do, appears Euclidean to those of us living within it, even though we’re still trying to figure out its global shape.
Even in cases where manifolds don’t seem to be present, mathematicians and physicists try to rewrite their problems in the language of manifolds to make use of their helpful properties. “So much of physics comes down to understanding geometry,” said Jonathan Sorce, a theoretical physicist at Princeton University. “And often in surprising ways.”
Consider a double pendulum, which consists of one pendulum hanging from the end of another. Small changes in the double pendulum’s initial conditions lead it to carve out very different trajectories through space, making its behavior hard to predict and understand. But if you represent the configuration of the pendulum with just two angles (one describing the position of each of its arms), then the space of all possible configurations looks like a doughnut, or torus — a manifold. Each point on this torus represents one possible state of the pendulum; paths on the torus represent the trajectories the pendulum might follow through space. This allows researchers to translate their physical questions about the pendulum into geometric ones, making them more intuitive and easier to solve. This is also how they study the movements of fluids, robots, quantum particles and more.
Similarly, mathematicians often view the solutions to complicated algebraic equations as a manifold to better understand their properties. And they analyze high-dimensional datasets — such as those recording the activity of thousands of neurons in the brain — by looking at how those data points might sit on a lower-dimensional manifold.
Asking how scientists use manifolds is akin to asking how they use numbers, Sorce said. “They are at the foundation of everything.”…
“What Is a Manifold?” from @quantamagazine.bsky.social.
Apposite: Rowińska in conversation with Ira Flatow on Science Friday: “How Math Helps Us Map The World.”
* David S. Richeson, Euler’s Gem: The Polyhedron Formula and the Birth of Topology (Riemann’s work was an advance on the foundation that Euler laid in his 1736 paper on the Seven Bridges of Königsberg, which led to his polyhedron formula)
###
As we get down with geometry, we might spare a thought for John Wallis; he died on this date in 1703. A clergyman and mathematician, he served as chief cryptographer for Parliament (decoding Royalist messages during the Civil War) and, later (as Savilian Chair of geometry at Oxford after the hostilities), for the the royal court. Wallis is credited with introducing the symbol ∞ to represent the concept of infinity, and used 1/∞ for an infinitesimal… which earned him (along with his contemporaries Isaac Newton and Gottfried Wilhelm Leibniz) a share of the credit for the development of infinitesimal calculus. He was a founding member of the Royal Society and one of its first Fellows.
“Make visible what, without you, might perhaps never have been seen”*…
Lawrence Weschler is no stranger to controversy. In 2000 he published an article in The New Yorker, recounting a theory that David Hockey had shared with him, that ignited a fire storm in the art world– and that burns (or at least smolders) to this day.
And he’s at it again…
A few months back—in the lee of the Rijksmuseum’s epic Vermeer show and Ren’s [Wechsler’s] controversial Atlantic magazine article (featured in our Issue #39) on Vermeer and Benjamin Binstock’s intriguing contention that eight of the thirty-four paintings conventionally attributed to the Delft master were in fact by his daughter Maria—the eminent curator Helen Molesworth invited Ren and Claudia Swan (the historian behind Rarities of These Lands and other classics on the Dutch Golden Age) to engage in a conversation evaluating both that show and Binstock’s thesis for an episode of her ongoing Dialogues podcast, out of the David Zwirner Gallery. And indeed, that half-hour episode dropped yesterday—and we thought you might enjoy hearing it here. Spoiler alert: Two of the top people in the field seem decidedly open to Binstock’s theory…
Fascinating: “Vermeer’s Daughter?”
* Robert Bresson
###
As we argue over attribution, we might send grateful birthday greetings to Leon Battista Alberti; he was born on this date in 1404. The archetypical Renaissance humanist polymath, Alberti was an author, artist, architect, poet, priest, linguist, philosopher, cartographer, and cryptographer. Indeed, with Johannes Trithemius, he is considered the father of cryptography. And he collaborated with Toscanelli on the maps used by Columbus on his first voyage.
But he is surely best remembered as the man who “wrote the book” on perspective: he authored of the first general treatise– De Pictura (1434)– on the the laws of perspective, which built on and extended Brunelleschi’s work to describe the approach and technique that established the science of projective geometry… and fueled the progress of painting, sculpture, and architecture from the Greek- and Arabic-influenced formalism of the High Middle Ages to the more naturalistic (and Latinate) styles of Renaissance.
“There are two types of encryption: one that will prevent your sister from reading your diary and one that will prevent your government”*…
… But sometimes the encryption you think will work against governments won’t even deter your sister. Joesph Cox on the recently-uncovered vulnerabilities in TETRA, the encryption standard used in radios worldwide…
A group of cybersecurity researchers has uncovered what they believe is an intentional backdoor in encrypted radios used by police, military, and critical infrastructure entities around the world. The backdoor may have existed for decades, potentially exposing a wealth of sensitive information transmitted across them, according to the researchers… The end result, however, are radios with traffic that can be decrypted using consumer hardware like an ordinary laptop in under a minute…
The research is the first public and in-depth analysis of the TErrestrial Trunked RAdio (TETRA) standard in the more than 20 years the standard has existed. Not all users of TETRA-powered radios use the specific encryption algorithim called TEA1 which is impacted by the backdoor. TEA1 is part of the TETRA standard approved for export to other countries. But the researchers also found other, multiple vulnerabilities across TETRA that could allow historical decryption of communications and deanonymization. TETRA-radio users in general include national police forces and emergency services in Europe; military organizations in Africa; and train operators in North America and critical infrastructure providers elsewhere.
Midnight Blue [presented] their findings at the Black Hat cybersecurity conference in August. The details of the talk have been closely under wraps, with the Black Hat website simply describing the briefing as a “Redacted Telecom Talk.” That reason for secrecy was in large part due to the unusually long disclosure process. Wetzels told Motherboard the team has been disclosing these vulnerabilities to impacted parties so they can be fixed for more than a year and a half. That included an initial meeting with Dutch police in January 2022, a meeting with the intelligence community later that month, and then the main bulk of providing information and mitigations being distributed to stakeholders. NLnet Foundation, an organization which funds “those with ideas to fix the internet,” financed the research.
The European Telecommunications Standards Institute (ETSI), an organization that standardizes technologies across the industry, first created TETRA in 1995. Since then, TETRA has been used in products, including radios, sold by Motorola, Airbus, and more. Crucially, TETRA is not open-source. Instead, it relies on what the researchers describe in their presentation slides as “secret, proprietary cryptography,” meaning it is typically difficult for outside experts to verify how secure the standard really is.
…
Bart Jacobs, a professor of security, privacy and identity, who did not work on the research itself but says he was briefed on it, said he hopes “this really is the end of closed, proprietary crypto, not based on open, publicly scrutinised standards.”…
The veil, pierced: “Researchers Find ‘Backdoor’ in Encrypted Police and Military Radios,” from @josephfcox in @motherboard. (Not long after this article ran– and after the downfall of Vice, Motherboard’s parent), Cox and a number of his talented Motherboard colleagues launched 404 Media. Check it out.)
Remarkably, some of the radio systems enabling critical infrastructure are even easier to hack– they aren’t even encrypted.
* Bruce Schneier (@schneierblog)
###
As we take precautions, we might recall that it was on this date in 1980 that the last IBM 7030 “Stretch” mainframe in active use is decommissioned at Brigham Young University. The first Stretch was was delivered to Los Alamos National Laboratory in 1961, giving the model almost 20 years of operational service.
The Stretch was famous for many things, but perhaps most notably it was the first IBM computer to use transistors instead of vacuum tubes; it was the first computer to be designed with the help of an earlier computer; and it was the world’s fastest computer from 1961 to 1964.
“The sciences of cryptography and mathematics are very elegant, pure sciences. I found that the ends for which these pure sciences are used are less elegant.”*…
Mary, Queen of Scots wrote 57 encrypted messages during her captivity in England; until recently, all but 7 of them were believed lost. Meilan Solly tells the tale of their discovery and decryption…
Over the course of her 19 years in captivity, Mary, Queen of Scots, wrote thousands of letters to ambassadors, government officials, fellow monarchs and conspirators alike. Most of these missives had the same underlying goal: securing the deposed Scottish queen’s freedom. After losing her throne in 1567, Mary had fled to England, hoping to find refuge at her cousin Elizabeth I’s court. (Mary’s paternal grandmother, Margaret Tudor, was the sister of Elizabeth’s father, Henry VIII.) Instead, the English queen imprisoned Mary, keeping her under house arrest for nearly two decades before ordering her execution in 1587.
Mary’s letters have long fascinated scholars and the public, providing a glimpse into her relentless efforts to secure her release. But the former queen’s correspondence often raises more questions than it answers, in part because Mary took extensive steps to hide her messages from the prying eyes of Elizabeth’s spies. In addition to folding the pages with a technique known as letterlocking, she employed ciphers and codes of varying complexity.
More than 400 years after Mary’s death, a chance discovery by a trio of code breakers is offering new insights into the queen’s final years. As the researchers write in the journal Cryptologia, they originally decided to examine a cache of coded notes housed at the National Library of France as part of a broader push to “locate, digitize, transcribe, decipher and analyze” historic ciphers. Those pages turned out to be 57 of Mary’s encrypted letters, the majority of which were sent to Michel de Castelnau, the French ambassador to England, between 1578 and 1584. All but seven were previously thought to be lost…
What they found and how they made sense of it: “Code Breakers Discover—and Decipher—Long-Lost Letters by Mary, Queen of Scots,” from @meilansolly in @SmithsonianMag.
* Jim Sanborn, the sculptor who created the encrypted Kryptos sculpture at CIA headquarters
###
As we crack codes, we might spare a thought for a rough contemporary of Mary’s, a man who refused to communicate in code: Giordano Bruno. A Dominican friar, philosopher, mathematician, and astronomer whose concept of the infinite universe expanded on Copernicus’s model, he was the first European to understand the universe as a continuum where the stars we see at night are identical in nature to the Sun. Bruno’s views were considered dangerously heretical by the (Roman) Inquisition, which imprisoned him in 1592; after eight years of refusals to recant, on this date in 1600, he was burned at the stake.
You must be logged in to post a comment.