## Finding the Multiplicative Inverse within a Modulus

The general concept in RSA Cryptography is, there exists a product of two prime numbers, call them (p) and (q), such that

(T ^ E) ^ D mod (p)(q) = T

where,

T is an original plaintext document,

E is an encryption key,

D is the corresponding decryption key,

E and D are successively-applied exponents, of T,

(p)(q) is the original modulus.

A famous Mathematician named Euler found, that in order for exponent operations on T to be consistent in the modulus (p)(q), the exponents’ product itself must be consistent in the modulus (p-1)(q-1). This latter value is also known as Euler’s Totient Product of (p)(q).

There is a little trick to this form of encryption, which I do not see explained often, but which is important. Since E is also the public key, a relatively small prime number is used in practice, that being (2^16 + 1), or 65537. D could be a 2048 or a 4096-bit exponent. The public key consists of the exponent E and the modulus (p)(q) packaged together.

Thus, when the key-pair is created, (p) and (q) must be known separately, so that D can be computed, and then (p-1)(q-1), which hopefully never touched the hard-drive, can be discarded, after D is saved, along with (p)(q) again, this time forming the private key.

Therefore, D must be the multiplicative inverse of E, in the modulus of (p-1)(q-1). But how does one compute that?

(Corrected 09/27/2018, 15h15 … )

## Bitcoin Basics

When a Bitcoin Wallet Program synchronizes its own list of Receiving Addresses, it broadcasts a query over the network, which names each Public Key / Address, and the network replies with an updated history, of whether that Address has Sent or Received any funds since the last sync, on the assumption that the same Bitcoin Wallet also stores the corresponding Private Keys. If the Wallet Program tries to Send any funds From one of its Addresses, it must Prove that it holds the Private Key, by Signing the request to do so, using Public Key Cryptography. This signature can be verified by anybody using only the Public Key.

If the stated Address has never received any funds, I believe that the query disappears from the network within some short amount of time.

It is common practice in Public Key Cryptography, additionally to encrypt any Private Keys using a Password which is not stored, and which the user must enter, every time he wants to use them, but not to encrypt the Public Keys. Since simply to receive an update for the Public Keys does not require the user enter his Password, it follows that the Wallet Program does not need to prove to the network, that it does have the Private Keys stored.

Otherwise, if the Wallet stores any Public Keys without the corresponding Private Key, by default, those are assumed to belong to other users, as potential Addresses to Send funds to. And this is about as much as a basic Bitcoin Wallet Program needs to be able to do.

However, most specific Wallet Programs have additional features and capabilities, specific to one Program. For example, some Wallet Programs allow for more than one Wallet to be created, and additionally allow for pure, Address-Watching Wallets to be created, which when synced, also query the network for a list of Addresses, but for which the Wallet in question does not store any Private Keys. These Wallets receive updates for the list of Addresses even though the Addresses in question are actually externally-owned, since the network never required any proof from the Program anyway, that it has the Private Keys.

I think the main disadvantage of this approach, is the fact that this separate Wallet does not get synced, unless the user specifically instructs his Program to Open that one.

But, since some programmers do not feel that their users need these advanced capabilities, certain Wallet Programs simply leave them out, especially in the case of Wallets meant for smart-phones. OTOH, smart-phone Wallets often have additional capabilities, related to being able to scan QR-codes, in order to acquire Addresses to Send To, or to acquire ‘Requests For Funds’, which in addition an Address, contain the Amount that should be Sent, within the same QR-code…

Dirk

## An Interesting Tool for creating Paper Wallets

I have written various postings now, about Bitcoin Wallets. One of the themes which I have brought up, is that the online account, of how much money has been Sent To and From a Bitcoin Address, is more important, than the offline account of it, which can therefore sometimes be reduced to only a Private Key and a Public Key. The Public Key can be converted to and from a Bitcoin Address to Send funds To, while the Private Key can be used to authorize, that funds be Sent From the same Address.

And so one subject which I also wrote about, is that if a person has the Private Key, he or she can use some existing Bitcoin Wallet apps, to Sweep that Address, thus giving the command to the network, to Send all its funds to another Address, which is online.

There is some minor discrepancy, between what I called an ‘Offline Wallet’, and what the Internet calls an “Offline Wallet”. What I was referring to by that term, would actually be called “A Wallet In Cold Storage”. What the Internet may refer to instead, is a kind of Wallet, being accessed by a program, but on a computer which is separated from the Internet by an Air Gap.

In reality, the subject of the security of Air Gap systems, is quite beyond what I am currently willing to write about. My personal guess is, that if most of us wanted that, we might be a bit too paranoid for the mundane world. There exist some organizations and even companies, who need Air Gap Systems, but then there is a whole rigamarole, of what needs to be done, for an Air Gap system actually to receive the full benefit, one hopes to gain by using them…

But, having done some reading, I have come across a tool which even everyday users could find useful, in creating an actual Paper Wallet:

Online Tool

Because all that is needed for one Bitcoin Address to exist, in principle, is a correctly-formatted set of Private and Public Keys, a tool can be useful somewhat, which only does that, and which offers to print those out as QR Codes. The above Link is a Web-page, which does this.

(Edit 10/08/2016 : Actually, I had previously posted a mistake here. As it stands, if a person transfers a Bitcoin-amount to an Address that is validly-formed, that amount will remain associated with the Address, even if no attempt is made to query the Address. This Bulletin-Board Conversation seems to state so.)

## Possible Misconception: Bitcoin Wallet Singular

There is a possible misconception which people might have about how Bitcoin Wallets work, which I would say, because I had this misconception myself until only very recently. Many popular Bitcoin Wallets present themselves to the user as having one balance at one time.

Each time we receive funds, most of the time, we will want to receive those funds to a separately-created Address. And the difference between the Address and the Public Key, is mainly one in formatting of the binary data.

What many Wallets do not show the user, is that each receiving Address continues to hold its own balance. This means that when we tell such a Wallet to Send an amount of Bitcoins to another recipient, which is larger than the balance we hold on any one of our own Addresses, what our Wallet tends to try to do, is to make numerous transactions, one from each Address, all to the same recipient, until the total amount of funds has reached the amount we asked to Send.

Each of those Addresses, being a Public Key, has its own Private Key, which we must unlock across-the-board, at least until the transaction is complete. And each Private Key, therefore, only has a limited amount of Funds it can Send. Balances are not allowed to go negative.

And so what can happen to many users, is that our Wallets become fragmented, with only a small balance associated with each of our Addresses, many of which might have started out as having a larger, received balance. And sometimes, the P2P network can be reluctant to process such a transaction, because it represents a load on the network.

And so an operation that some Wallets recommend, is that if we have many small balances, eventually to transfer a larger sum, out of those balances, to a new, single receiving Address we have in our own, same Bitcoin Wallet. This incurs the transaction fee normally associated with such an operation, but the only benefit to us, is that we will have a single, larger balance afterward.

Other types of Wallets do not show us, how much of our balance is associated with each Address.

What this also means, in connection with what I wrote before, about being able to Sweep one Address, is that this ability is usually not so sweeping in practice. Since a wallet with 10 Addresses that hold balances, can also have 10 Private Keys, the program from which we might want to do the Sweeping, will need each of the Private Keys, in order to empty out a whole Wallet, for example.

From the security perspective, it could become a more complicated action, to steal 10 Private Keys, than it would have been simply to Steal 1 Private Key. And for off-line Wallets, this can be a limiting factor. We can only write down a limited number of Private Keys by hand, on a sheet of paper, for example.

Dirk