How does NAT ensure that every machine has a unique public IP?
It does not.
Your question is more complicated than you seem to imagine. The range from which public addresses are drawn is 1.0.0.0 to 223.255.255.255, but there are some blocks within that range that cannot be used for public addresses.
IANA maintains the IANA IPv4 Special-Purpose Address Registry that explains for each of the blocks if addresses in a block can be used as source or destination addresses, whether the addresses are forwardable (routable), and whether the addresses are globally reachable. Some addresses, e.g. 127.0.0.0/8, are reserved by the IPv4 protocol itself, and that is also indicated. Other address blocks are not globally reachable because the ISPs have agreed to not forward them on the public Internet. For example, the three Private address blocks were arbitrarily chosen, and the ISPs agree to not forward them on the public Internet, but they can be forwarded within a private network, including an ISP's own network, but not between the ISP networks, although two ISPs (or other companies) can agree to forward them between the two ISPs.
The addresses that are globally reachable are known as public addresses. IANA owns these addresses, and it assigns them to RIRs for use within a region. The RIRs assign these addresses to companies, including ISPs. Unfortunately, IANA ran out of addresses to assign to the RIRs, and the RIRs have since run out of addresses to assign to companies within their regions.
The biggest mitigation for the IPv4 address shortage is the use of one form of NAT called NAPT. It allows companies without enough public IPv4 addresses to hide other addressing behind a single public address. As you have noted, this does cause problems for traffic initiated outside the private addressing. There are various methods to try to get around this problem, but it is a problem.
My question is, how exactly does NAT perform this transformation? Some
sources that I saw suggested that each machine would use the public IP
of the router, but this cannot be true.
That really is true for NAPT. What you are missing is that many companies are assigned blocks of public addressing, and they use their public addresses for devices needing to be reached from outside the company, and other devices that only need to initiate a conversation will use private addressing that translates to a public address.
Does every machine have a unique public IP address or not?
No. There are devices that do not connect to the public Internet at all, only to internal networks, and there is no need to publicly address those devices. Other devices may sometimes need to access services on the public Internet, and those devices can use private addressing and NAPT (although NAPT can be a big problem for some applications and protocols). Other devices need to provide services to the public Internet, and those devices will have a public address, ether directly assigned to the device, or the device many have a private address with a permanent entry in the NAPT table of the publicly connected router.
If not, how are different machines on a network distinguished by an
machine that is not on the same network?
In most cases, they are not distinguished. The original IP paradigm was that every device have a unique (public) address. There are not enough public IPv4 addresses to even come close to this. The use of IPv4 Private addressing and NAPT is a workaround, but you sacrifice the end-to-end connectivity of IP by requiring devices in the middle to maintain the state of the connection. For some devices, you can add a permanent entry in the NAPT table to allow outside-initiated traffic to be sent to a particular device on the inside. (Inside-initiated traffic automatically creates an entry in the NAPT table to allow replies.)
NAPT only works with TCP, UDP, and ICMP. Other transport protocols fail, and some applications and application-layer protocols that use TCP or UDP can also break because of NAPT.
NAT (including NAPT) is a huge subject, and there are multiple RFCs that cover it. For example, RFC 3022, Traditional IP Network Address Translator (Traditional NAT), where Section 2.2 discusses NAPT:
2.2. Overview of NAPT
Say, an organization has a private IP network and a WAN link to a
service provider. The private network's stub router is assigned a
globally valid address on the WAN link and the remaining nodes in the
organization have IP addresses that have only local significance. In
such a case, nodes on the private network could be allowed
simultaneous access to the external network, using the single
registered IP address with the aid of NAPT. NAPT would allow mapping
of tuples of the type (local IP addresses, local TU port number) to
tuples of the type (registered IP address, assigned TU port number).
This model fits the requirements of most Small Office Home Office
(SOHO) groups to access external network using a single service
provider assigned IP address. This model could be extended to allow
inbound access by statically mapping a local node per each service TU
port of the registered IP address.
In the example of figure 3 below, stub A internally uses class A
address block 10.0.0.0/8. The stub router's WAN interface is assigned
an IP address 138.76.28.4 by the service provider.
\ | /
+-----------------------+
|Service Provider Router|
+-----------------------+
WAN |
|
Stub A .............|....
|
^{s=138.76.28.4,sport=1024, | v{s=138.76.29.7, sport = 23,
^ d=138.76.29.7,dport=23} | v d=138.76.28.4, dport = 1024}
+------------------+
|Stub Router w/NAPT|
+------------------+
|
| LAN
--------------------------------------------
| ^{s=10.0.0.10,sport=3017, | v{s=138.76.29.7, sport=23,
| ^ d=138.76.29.7,dport=23} | v d=10.0.0.10, dport=3017}
| |
+--+ +--+ +--+
|--| |--| |--|
/____\ /____\ /____\
10.0.0.1 10.0.0.2 ..... 10.0.0.10
Figure 3: Network Address Port Translation (NAPT) Operation
When stub A host 10.0.0.10 sends a telnet packet to host 138.76.29.7,
it uses the globally unique address 138.76.29.7 as destination, and
sends the packet to it's primary router. The stub router has a static
route for the subnet 138.76.0.0/16 so the packet is forwarded to the
WAN-link. However, NAPT translates the tuple of source address
10.0.0.10 and source TCP port 3017 in the IP and TCP headers into the globally unique 138.76.28.4 and a uniquely assigned TCP port, say
1024, before the packet is forwarded. Packets on the return path go
through similar address and TCP port translations for the target IP
address and target TCP port. Once again, notice that this requires no
changes to hosts or routers. The translation is completely
transparent.
In this setup, only TCP/UDP sessions are allowed and must originate
from the local network. However, there are services such as DNS that
demand inbound access. There may be other services for which an
organization wishes to allow inbound session access. It is possible
to statically configure a well known TU port service [RFC 1700] on the
stub router to be directed to a specific node in the private network.
In addition to TCP/UDP sessions, ICMP messages, with the exception of
REDIRECT message type may also be monitored by NAPT router. ICMP query
type packets are translated similar to that of TCP/UDP packets, in
that the identifier field in ICMP message header will be uniquely
mapped to a query identifier of the registered IP address. The
identifier field in ICMP query messages is set by Query sender and
returned unchanged in response message from the Query responder. So,
the tuple of (Local IP address, local ICMP query identifier) is mapped
to a tuple of (registered IP address, assigned ICMP query Identifier)
by the NAPT router to uniquely identify ICMP queries of all types from
any of the local hosts. Modifications to ICMP error messages are
discussed in a later section, as that involves modifications to ICMP
payload as well as the IP and ICMP headers.
In NAPT setup, where the registered IP address is the same as the IP
address of the stub router WAN interface, the router has to be sure to
make distinction between TCP, UDP or ICMP query sessions originated
from itself versus those originated from the nodes on local network.
All inbound sessions (including TCP, UDP and ICMP query sessions) are
assumed to be directed to the NAT router as the end node, unless the
target service port is statically mapped to a different node in the
local network.
Sessions other than TCP, UDP and ICMP query type are simply not
permitted from local nodes, serviced by a NAPT router.
