It's been a while since I researched this topic, however, several algorithms exist. At the time of my research (3 years ago), the A5 algorithm was the most used algorithm in Europe for phone and sms conversations (GPRS used a different algorithm). Several variations exist:
- A5/1: most widely used (deemed the most secure of the three), but cracked by Karsten Nohl in 2009-2010
I am not sure if these algorithms are still in use, but I assume the encryption/authentication is still done in a similar manner. Update: the 3G and 4G are probably a lot safer. However, operators often fallback to 2G for normal calls/SMSes. The A5/3 algorithm (aka KASUMI) is said to be used in 3G communications. KASUMI is much harder to crack, and thus it is more simple for the NSA to go and steal the keys. Update 2: by operating a jamming device, agencies have reportedly disrupted 3G/4G communications, causing nearby phones to fall back to crackable 2G.
To decide whether or not the SIM may access the network, the SIM needs to be authenticated. A random number is generated by the operator, and is sent to the mobile device. Together with the secret key Ki, this random number runs through the A3 algorithm (it is this Ki that recently has been compromised). The output of this calculation is sent back to the operator, where the output is compared with the calculation that the operator has executed himself (the operator possesses the secret keys for all SIM cards the operator has distributed).
This part is the part that has been cracked. In short, the operator generates a random number (again), and sends it to the mobile phone. Together with the secret key Ki, this random number runs through the A8 algorithm, and generates a session key KC. This KC is used, in combination with the A5 algorithm to encrypt/decrypt the data.
Note: the figure is from a paper by SANS institute, and the explanation of the A5 algorithm crack is based on the presentation of Karsten Nohl. I cannot seem to find a valid link to both of these papers at the moment.