Verifying a downloaded file’s hash in PowerShell

I downloaded the Cwtch beta and I wanted to verify the hash of the downloaded file against the published hash on the download page.

These are the commands I ran and their output:

> $expected = "(sha-512 hash from website)";
> $actual = (get-filehash "(path-to-downloaded-file)" -algorithm sha512).Hash;
> $actual -eq $expected
True

Get-FileHash defaults to SHA-256, but the published hash is SHA-512, so the -Algorithm parameter is necessary here.

Making ())( not a palindrome anymore – defining “conjugate palindromicity”

One of the top posts on r/Showerthoughts is It’s off-putting that ()() isn’t a palindrome, yet ())( is.

I agree.

The absolute value operator |x| is first taught as “if x is negative, make it positive.” This falls apart with complex numbers. Then |z| is retaught as “multiply z by its conjugate, then take the square root of the result.”

What is “the conjugate of z?” Complex numbers come in conjugate pairs; think of them as opposite sides of the same coin. -1 has two square roots: i and –i. The conjugate of z is the number you get by choosing the other square root. For example, the conjugate of -3 – 4i is -3 + 4i.

In much the same way, English (and other languages) have conjugate symbols. Just as -3 – 4i and -3 + 4i are a conjugate pair, so too are ( and ) a conjugate pair.

The usual definition of a “palindrome” is “a sequence of symbols that reads the same forwards and backwards” which is to say “a sequence that is identical to its own reverse.” The sequence is symmetric under the operation of reversal. With this definition, ()() is not a palindrome, and ())( is. That can’t be right, so the definition is wrong.

The way conjugate symbols work is fundamentally tied to their position in the sequence. A ( at the beginning of the string means the same, in reverse, as a ) at the end of the string. So I make a new definition – conjugate palindromicity. A sequence of symbols is a conjugate palindrome if it is symmetric under the operation of reversal and the replacement of all symbols with their conjugate.

I wrote a PowerShell script which tests strings for both palindromicity and conjugate palindromicity.

Test-Palindrome.ps1

> .\Test-Palindrome.ps1 "()()"; .\Test-Palindrome.ps1 "())("; .\Test-Palindrome.ps1 "()()" -conjugate; .\Test-Palindrome.ps1 "())(" -conjugate
False
True
True
False

Under this new definition, happily, ()() is a conjugate palindrome, and ())( is not (as it should not be.)

Reversal and conjugation applied to ()() and ())(

Bipartisan-ness of United States presidential impeachment verdicts

Yesterday the United States Senate voted on whether to convict former President Donald Trump of the impeachment charge brought against him by the House.

I have heard two claims being made about this verdict:

  • This is the “most bipartisan” impeachment in US history
  • This impeachment “brought the most guilty votes” in US history

There have been four impeachment verdicts against United States Presidents by the United States Senate. Here’s the data:

  • Andrew Johnson, 1868
    • Verdict: not guilty on all counts
    • 54 Senators
      • 45 Republican
      • 9 Democratic
    • Vote: 35 guilty, 19 not guilty
      • Guilty: 35 Republican
      • Not guilty: 10 Republican, 9 Democratic
  • Bill Clinton, 1999
    • Verdict: not guilty on all counts
    • 100 Senators
      • 55 Republican
      • 45 Democratic
    • On the “perjury” count
      • 45 guilty, 55 not guilty
        • Guilty: 45 Republican
        • Not guilty: 45 Democratic, 10 Republican
    • On the “obstruction of justice” count
      • 50 guilty, 50 not guilty
        • Guilty: 50 Republican
        • Not guilty: 45 Democratic, 5 Republican
  • Donald Trump, 2020
    • Verdict: not guilty on all counts
    • 100 Senators
      • 53 Republican
      • 45 Democratic
      • 2 Independent
    • On the “abuse of power” count
      • 48 guilty, 52 not guilty
        • Guilty: 45 Democratic, 1 Republican, 2 Independent
        • Not guilty: 52 Republican
    • On the “obstruction of justice” count
      • 47 guilty, 53 not guilty
        • Guilty: 45 Democratic, 2 Independent
        • Not guilty: 53 Republican
  • Donald Trump, 2021
    • Verdict: not guilty (on the sole count)
    • 100 Senators
      • 50 Democratic
      • 50 Republican
    • 57 guilty, 43 not guilty
      • Guilty: 50 Democratic, 7 Republican
      • Not guilty: 43 Republican

The “most bipartisan” claim is mostly true though it ignores the role of the two Independent Senators in Donald Trump’s 2020 impeachment verdict.

The “most guilty votes” claim is misleading. Yes, it is technically true that Donald Trump 2021’s 57 guilty votes is more by count than Andrew Johson 1868’s 35 guilty votes – but as a percentage Andrew Johnson’s 65% guilty is higher than Donald Trump 2021’s 57% guilty.

So Andrew Johnson still has the honor of being the President who came closest to being convicted by the Senate.

How all the United States presidencies have ended

There are lots of ways a United States presidency can come to an end. Let’s look at some of them.

Did not run for re-election

20 presidents have chosen not to run for re-election when their term expired. (I also include cases where a president sought re-election but was not nominated.)

  1. George Washington, 1796
  2. Thomas Jefferson, 1808
  3. James Madison, 1816
  4. James Monroe, 1824
  5. Andrew Jackson, 1836
  6. John Tyler, 1844
  7. James K. Polk, 1848
  8. Millard Fillmore, 1852
  9. Franklin Pierce, 1856
  10. James Buchanan, 1860
  11. Andrew Johnson, 1868
  12. Ulysses S. Grant, 1876
  13. Rutherford B. Hayes, 1880
  14. Chester A. Arthur, 1884
  15. Grover Cleveland (second term,) 1896
  16. Theodore Roosevelt, 1908
  17. Woodrow Wilson, 1920
  18. Calvin Coolidge, 1928
  19. Harry S. Truman, 1952
  20. Lyndon B. Johnson, 1968

Lost re-election

Eleven presidents have run for re-election but lost. Grover Cleveland later ran again and won.

  1. John Adams, 1800
  2. John Quincy Adams, 1828
  3. Martin van Buren, 1840
  4. Grover Cleveland (first term,) 1888
  5. Benjamin Harrison, 1892
  6. William Howard Taft, 1912
  7. Herbert Hoover, 1932
  8. Gerald Ford, 1976
  9. Jimmy Carter, 1980
  10. George H. W. Bush, 1992
  11. Donald Trump, 2020

Died in office

Eight presidents have died while in office.

  1. William Henry Harrison, 1841
  2. Zachary Taylor, 1850
  3. Abraham Lincoln, 1865
  4. James A. Garfield, 1881
  5. William McKinley, 1901
  6. Warren G. Harding, 1923
  7. Franklin D. Roosevelt, 1945
  8. John F. Kennedy, 1963

Exhausted term limits

In 1951 the 22nd amendment to the United States Constitution instituted term limits for the presidency. Five presidents have exhausted those term limits.

  1. Dwight D. Eisenhower, 1960
  2. Ronald Reagan, 1988
  3. Bill Clinton, 2000
  4. George W. Bush, 2008
  5. Barack Obama, 2016

Resigned

One president has resigned.

  1. Richard Nixon, 1974

Impeached and removed

Article I of the Constitution lays out a process for impeachment (by the House) and removal (by the Senate) of a president. Impeachment has happened four times, but removal has not happened:

  1. Andrew Johnson, 1868 (acquitted)
  2. Bill Clinton, 1998 (acquitted)
  3. Donald Trump, 2019 (acquitted); 2021 (term ended prior to trial)

Unable to discharge powers and duties

Article II of the Constitution, as amended in 1967 by the 25th amendment, lays out a process by which the Vice President can become Acting President if the President is “unable to discharge the powers and duties of his office.” This has not happened.

EDIT 2021-01-13: Impeachment has happened four times now.

EDIT 2021-01-20: Donald Trump’s term has officially ended via “lost re-election.”

Gender identity and sexual attraction, part 3 – vocabulary for attraction in the triangle gender model

Posts in this series:

We can extend much of the continuum vocabulary forward, with careful consideration to agender/genderless and partially gendered people. There will be some ambiguity, and some outright gaps, some of which we will attempt to fill with new vocabulary.

For example:

  • Consider neptunic.
    • Continuum definition: a person (of any gender) who desires people who are female or nonbinary is neptunic.
    • Triangle definition: A person (of any or no gender) who desires people who are female, nonbinary, or agender/genderless, is neptunic.
  • Consider mercuric.
    • Continuum definition: a person (of any gender) who desires people who are female or male is mercuric.
    • Triangle definition: this could extend in two different ways. It could include agender/genderless people, or not. For the purposes of this blog post we will extend it to not include agender/genderless people; this means we need a new term for the other possible extension.
  • Consider a person who is attracted only to agender/genderless people. There is no term in the continuum model which would naturally extend to this; we need a new word.
  • The continuum model had several words which applied only if the desirer was male, or female, or nonbinary. We need new terms for agender/genderless desirers.

Terms for attraction by gender of the desired

In addition to all the terms carried forward, we add the following:

Here’s a diagram:

Terms for attraction to particular gender combinations in the triangle model

Terms for attraction if the desirer is agender/genderless

If the desirer is agender/genderless, we add the following terms:

  • An agender/genderless person who desires people regardless of gender or lack thereof is dahlian.
  • An agender/genderless person who desires agender/genderless people is delphinian.
  • An agender/genderless person who desires women is azalian.
  • An agender/genderless person who desires men is thistlian.
  • An agender/genderless person who desires gendered nonmen is plumerian.
  • An agender/genderless person who desires nonbinary people is wisterian.
  • An agender/genderless person who desires gendered nonwomen is lilacian.
  • An agender/genderless person who desires nonmen is geranian.
  • An agender/genderless person who desires nonwomen is irisian.
  • An agender/genderless person who desires men or women is orchidian.
  • An agender/genderless person who desires agender/genderless and nonbinary people is magnolian.

Here’s a diagram:

Terms for attraction to particular gender combinations in the triangle model if the desirer is agender/genderless

The terms magnolian, plumerian, wisterian, and lilacian appear to be lacking non-desirer-gender-specific equivalents. If you know of any, please tell me. I suppose, in the absence of specific terms, a male person who desired female people and nonbinary people could call himself a male plumerian, in the same way that some trixic people call themselves nonbinary lesbians.

Deep breath

(hands over ears)

OMG

WORD OVERLOAD

SO MANY WORDS

STOP WITH THE WORDS ALREADY

SEX IS SUPPOSED TO BE FUN

I feel a bit like J. Evans Pritchard, Ph. D. I have drowned human love in a sea of vocabulary and stretched it out to dry on mathematical axes. Please rip out these blog posts and go read a good love story.

Rip it out! — Dead Poets Society

but anyway

… those are some of the labels for people (perhaps of a particular gender, or perhaps not) who desire other people in particular combinations of genders.

It is likely that this post contains mistakes. If you find any please let me know.

Gender identity and sexual attraction, part 2 – vocabulary for attraction in the continuum gender model

Posts in this series:

Some words are used to describe desire for particular genders, regardless of the gender of the desirer:

Terms for attraction by gender of the desired

People whose desire is not defined by the gender of the desired:

  • A person (of any gender) who desires people of all genders is pansexual or omnisexual.
    • The binary model used bisexual for people who fit this definition. But since there are more than two genders, the bi- prefix doesn’t really fit here anymore.
  • A person (of any gender) who does not desire people is asexual.

People who desire one gender in particular:

  • A person (of any gender) who desires people who are female is venusic or womasexual.
  • A person (of any gender) who desires people who are male is marsic or masexual.
  • A person (of any gender) who desires people who are nonbinary is ceterosexual or enboric or stellaric. The term skoliosexual is now frowned upon because skolios can mean “crooked.” Allotroposexual is another potential alternative.

People who desire some specific combination of genders:

  • A person (of any gender) who desires people who are female or nonbinary is neptunic.
  • A person (of any gender) who desires people who are male or nonbinary is uranic.
  • A person (of any gender who desires people who are female or male is mercuric.
    • The binary model used bisexual for people who fit this definition too. So in the new model, bisexual is ambiguous. Best not to use it.

Here’s a diagram:

Terms for attraction to particular gender combinations in the continuum model

There are also terms which are specific to the gender of the desirer.

Terms for attraction if the desirer is male

If the desirer is male additional terms can be used:

  • A male who desires people regardless of gender is astronic or marblic.
  • A male who desires people who are female is mlw or straight.
  • A male who desires people who are female or nonbinary is litian.
  • A male who desires people who are male is achillean, gay, hyacique, mlm, vincian, or wildean although achillean is frowned upon by some because of Achilles’ non-consensual relationship with his slave-woman Briseis.
  • A male who desires people who are nonbinary is asteroidian, astroidian, or mlnb.
  • A nonbinary male who desires people who are female is umbalian.
  • A nonbinary male who desires people who are male is azurian.

Here’s a diagram:

Terms for attraction to particular gender combinations in the continuum model if the desirer is male

Terms for attraction if the desirer is female

If the desirer is female additional terms can be used:

  • A female who desires people who are female is lesbian or sapphic or wlw.
  • A female who desires people who are female or nonbinary is agatic.
  • A female who desires people who are male is straight or wlm.
  • A female who desires people who are male or nonbinary is citrinian.
  • A female who desires people who are nonbinary is asterian or wlnb.

Here is a diagram:

Terms for attraction to particular gender combinations in the continuum model if the desirer is female

Terms for attraction if the desirer is nonbinary

Here is a diagram:

Terms for attraction to particular gender combinations in the continuum model if the desirer is nonbinary

Okay that’s a lot of words.

Next time… even more words. Sorry.

It is likely that this post contains mistakes. If you find any please let me know.

Gender identity and sexual attraction, part 1 – models for gender identity

Posts in this series:

Last time I presented a couple of flowcharts for sexual attraction. But they weren’t really adequate. So let’s dig into gender identity a little.

To set the tone, here is Irving Kaufman singing Edgar Leslie and James Monaco’s 1925 song “Masculine Women! Feminine Men!”

Masculine Women! Feminine Men!

I present three models for gender identity.

It’s important to realize that these are just models. We’re going to try to use them to describe people, but the people are the important thing – not the model. If a real person and an artificial model don’t fit together, it is the model that is at fault, not the person.

Binary model

The binary model I grew up with admits of only two genders. It is useful only as a starting point for further development.

Binary gender model

We can express this mathematically as G2 = {♀, ♂}. We can define some labels:

  • A female person has gender ♀.
  • A male person has gender ♂.

Ugh. Surely we can do better than this.

Continuum model

The continuum model extends the binary model by creating a continuous spectrum of genders between the two genders in the binary model. This allows for more meaningful discourse but is still flawed.

Continuum gender model

We can express this mathematically as Gc = { (1 − λ)♀ + λ♂ | λ ∈ [0, 1] }. λ tells us the relative position of the gender compared to the binary genders ♀ and ♂. The model reduces to G2 in the case where λ ∈ {0, 1}.

We can define some labels:

  • A female person has λ near 0.
  • A male person has λ near 1.
  • A nonbinary person has λ away from 0 and 1.

The Galactian Alignments system allows for gender alignment of nonbinary people:

  • A female-aligned nonbinary person is lunarian.
  • A male-aligned nonbinary person is solarian.
  • A non-aligned nonbinary person is stellarian.

Here’s the same diagram showing the labels.

Gender continuum with labels

That’s a little better.

Triangle model

The triangle model extends the continuum model by adding a notion of gender saturation:

Triangle gender model

To express this mathematically we introduce ⚪ – meaning agender/genderlessness – and identify it with 0. We define the triangle GΔ = { κ((1 − λ)♀ + λ♂) | κ, λ ∈ [0, 1] }. κ is the degree of gender saturation. This reduces to the continuum model Gc in the case where κ = 1.

New definitions:

  • A gendered person has κ near 1.
  • An agender/genderless person has κ near 0.
  • A partially gendered person has κ away from 0 and 1.
  • A female person has (λ, κ) near (0, 1).
  • A male person has (λ, κ) near (1, 1).

Here’s the same diagram showing the labels:

Triangle gender model with labels

Better still.

Now, even this model is flawed – for example, it doesn’t fit with genderfluid or bimodal people – but I’ll stop here for the sake of space.

It is likely that, even as far as it goes, this post contains mistakes. If you find any please let me know.

Exercise: are agender/genderless people nonbinary?

Some sexual identification flowcharts

Here’s a sexual identification flowchart I made based on the binary gender model I grew up with:

Sexual identification flowchart

This is inadequate because it does not acknowledge the existence of:

  • People who are neither simply “male” nor simply “female”
  • People who don’t want to have sex

So I made an updated version:

I said the REAL sexual identification flowchart

That’s a little better. But I like this one best of all:

Perfection

Next time, more on the “this gets interesting” bit.

Hacking private keys from unsafe primes using the Pohlig-Hellman discrete logarithm

I’ve talked a few times about ElGamal encryption, where a participant A has a private key a and a public key ga mod p for some public prime p and generator g.

Now let’s suppose we’re an attacker and we’re after A‘s private key. We know her public key ga, we know g, and we know p. Can we figure out a = logg ga mod p? This is called the “discrete logarithm problem.”

Brute force

If p is extremely small or we are extremely patient we can do it very easily. Start with 1 = g0. Multiply by g to get g. Multiply again to get g2 mod p. Multiply a third time to get g3 mod p. Keep going until you get ga. Then a is just the number of times you had to multiply.

For example, consider implementing ElGamal encrypt, decrypt, sign, and verify signature. In this toy example p = 101, g = 2, A‘s private key was 57, and her public key was 257 mod 101 = 74. Since we (as the attacker) know g and p we can just calculate, doubling as we go, and subtracting 101 when we can:

  • 20 mod 101 = 1
  • 21 mod 101 = 2
  • 22 mod 101 = 4
  • 26 mod 101 = 64
  • 27 mod 101 = 27
  • 28 mod 101 = 54
  • 256 mod 101 = 37
  • 257 mod 101 = 74

So log2 74 = 57 mod 101 and now we know A‘s private key.

This approach takes O(p) time so it quickly becomes impractical as p gets big.

Baby-step giant-step

I blogged earlier about a speed improvement: David Shanks’ baby-step/giant-step algorithm. The basic idea is to precompute gi mod p only up to s = ⌈√p⌉ and then store them in a lookup table. Then use a little algebra to query the lookup table up to s times. This takes O(√p) time and space so it can let us squeeze out a little more juice but as √p gets big too this also becomes impractical.

Pohlig-Hellman

Stephen Pohlig and Martin Hellman (yes, that Hellman) published their algorithm for taking discrete logarithms which works by analyzing the group Zpx.

The group has p – 1 elements {1, 2, …, p – 1}. (Note that 0 is not included.) This means that the order of the subgroup generated by any given element divides p – 1.

Factor p – 1 as a product of powers of primes: p – 1 = p1k1 p2k2pnkn.

To calculate y = logg x mod p:

  1. Calculate y mod p1k1 (more on this later)
  2. Calculate y mod p2k2
  3. Calculate y mod pnkn
  4. Use the Chinese Remainder Theorem to reassemble y from its various modular residues.

That’s all well and good, but how do we calculate y mod piki?

Let q = pi and let k = ki. The trick to the algorithm is to realize that y mod qk can be written in base q as y0 + y1 q + y2 q2 + … + yk – 1 qk – 1. Each of the yi is a number in {0, 1, …, q – 1} and can be evaluated in O(√q) time and space using a little algebra, e.g. the fact that g(p – 1)/q is an element of order q.

So even if p is big, if p – 1 has all small prime factors, private keys can be extracted from public keys very quickly!

I wrote up an implementation of Pohlig-Hellman in PowerShell and tested it out.

First I found a (p – 1, p) pair where p was reasonably big and p – 1 had all small prime factors:

> cd pohlig-hellman
> .\find-unsafe-prime.ps1 -n 10000000
Sieving primes up to 10000000 + 1...
Finding largest small prime and the product of small primes from 100000000000000 to 100000020000000
Finding the prime between 100000000000000 and 100000020000000 with the smoothest p - 1
Prime 100000008359681 is one more than a number whose biggest prime factor is 53
> $p = [bigint]::Parse("100000008359681")
> $p
100000008359681 

100000008359681 is prime, and 100000008359680 = 28 5 112 13 19 31 37 43 53 has only small prime factors.

Then I found a generator:

> .\find-generator.ps1 -p 100000008359681
2^((100000008359681 - 1)/2) mod 100000008359681 = 1, rejecting 2
3^((100000008359681 - 1)/5) mod 100000008359681 = 1, rejecting 3
4^((100000008359681 - 1)/2) mod 100000008359681 = 1, rejecting 4
5^((100000008359681 - 1)/2) mod 100000008359681 = 1, rejecting 5
6 passes all checks
> $g = [bigint]::Parse("6")
> $g
6

Then I (arbitrarily) picked public key 6a = 2 mod 100000008359681. Now I have enough to calculate the discrete logarithm to find the private key a.

Actually, √p is still small enough that baby-step giant-step can crack this logarithm directly, but it is slow. On my machine it finds log6 2 = 67708279093016 mod 100000008359681 in a little over eleven minutes:

> cd baby-step-giant-step
> Measure-Command { .\baby-step-giant-step.ps1 -p $p -g $g -x 2 }
Find y so that 6^y = 2 mod 100000008359681
log_6 2 mod 100000008359681 = 67708279093016
6^67708279093016 mod 100000008359681 = 2
...
TotalMinutes      : 11.3536922983333
...

By comparison, Pohlig-Hellman finds the same logarithm on the same machine in less than one-tenth of a second:

> cd pohlig-hellman
> Measure-Command { .\pohlig-hellman.ps1 -p $p -g $g -x 2 }
log_6 2 = 67708279093016 mod 100000008359681
6^67708279093016 = 2 mod 100000008359681
...
TotalMilliseconds : 74.797
...

Solving x = r₁ mod m₁, x = r₂ mod m₂, … x = rₙ mod mₙ using the Chinese Remainder Theorem

Suppose we have an unknown number of objects. When counted in threes, 2 are left over, when counted in fives, 3 are left over, and when counted in sevens, 2 are left over. How many objects are there?

Sunzi Suanjing, 3rd to 5th century CE

I coded up a PowerShell implementation of the Chinese Remainder Theorem which solves sets of simultaneous modular equations like this. The above story problem can be translated as:

Find x that satisfies the following modular equations:

  • x = 2 mod 3
  • x = 3 mod 5
  • x = 2 mod 7

The answer it comes up with is 23:

> .\chinese-remainder-theorem.ps1 -moduli (3, 5, 7) -remainders (2, 3, 2)
23

Checking, this does indeed meet the criteria:

  • 23 = 3(7) + 2 = 2 mod 3
  • 23 = 5(4) + 3 = 3 mod 5
  • 23 = 7(3) + 2 = 2 mod 7

Actually, combining the equations only tells us that x = 23 mod 105. There are infinitely many such x, in particular 23, 128, 233, 338, …. The general term is 23 + 105n.