W momencie złamania kodów Enigmy Rejewski miał zaledwie 27 lat i stosunkowo niewielkie doświadczenie kryptologiczne. Pod koniec studiów matematycznych uczestniczył w trzymiesięcznym kursie kryptologicznym, zorganizowanym dla studentów Uniwersytetu Poznańskiego przez Oddział II Sztabu Głównego Wojska Polskiego, czyli polski wywiad wojskowy (kurs trwał od 15 stycznia do 22 marca 1929 r.), gdzie nauczono go podstaw łamania szyfrów.
Kurs obejmował podstawy kryptologii oraz działy matematyki wykorzystywane przy deszyfrażu, w tym m.in. permutacje i rachunek prawdopodobieństwa. Po latach Rejewski twierdził, że nie uczestniczył w całym kursie, ponieważ w obliczu innych obowiązków musiał przerwać swój udział w tym przedsięwzięciu. Po studiach wyjechał na rok do niemieckiej Getyngi, gdzie zapisał się na dwuletnie studia podyplomowe z matematyki ubezpieczeniowej. Po roku przedwcześnie je przerwał, wrócił do kraju i podjął pracę w charakterze młodszego asystenta w Instytucie Matematyki Uniwersytetu Poznańskiego.
Równolegle z karierą naukową nawiązał kontakt z wywiadem, pracując po kilka godzin dwa razy w tygodniu w poznańskiej placówce Biura Szyfrów, ulokowanej przy tamtejszym posterunku oficerskim Oddziału II (wywiadu). W swoich wspomnieniach pisał o tym następująco:
„W pracy naszej w ekspozyturze nie byliśmy krępowani żadnymi godzinami, każdy mógł pracować, kiedy mu było najdogodniej, z tym tylko, że każdy winien był przepracować 12 godzin tygodniowo”.
Co warte podkreślenia, w okresie tym nie wiedział jeszcze nic o niemieckiej maszynie szyfrującej Enigma, zajmował się łamaniem szyfrów ręcznych stosowanych przez niemiecką armię.
Przygoda z nowym szyfrem
Ze sprawą Enigmy został zapoznany dopiero jesienią 1932 r., gdy przeprowadził się do Warszawy. Przenosiny były następstwem likwidacji w Poznaniu przedstawicielstwa Biura Szyfrów. Jego trzem pracownikom zaproponowano pracę w stolicy, wobec czego od 1 września 1932 r. Marian Rejewski, Jerzy Różycki i Henryk Zygalski rozpoczęli pracę w centrali wywiadu, która znajdowała się w Pałacu Saskim. Początkowo również tam rozwiązywali szyfry ręczne, tym razem niemieckiej marynarki wojennej.
Dopiero po pewnym czasie Rejewski został wtajemniczony w sprawę maszyny szyfrującej i to rozpoczęło jego przygodę z Enigmą. W swoich wspomnieniach pisał o tym w następujący sposób:
„Zanim jeszcze ukończyliśmy pracę nad rozwiązaniem kodu morskiego, zlecono mi nową pracę, początkowo dodatkowo w godzinach wieczornych, później – gdy otrzymałem pierwsze pozytywne wyniki – w normalnych godzinach urzędowania. Dostarczono mi dość obfity materiał zaszyfrowany nowym rodzajem szyfru używanym przez niemieckie wojsko lądowe. Szyfr pojawił się – jeżeli się nie mylę – kilka lat wcześniej. Przypuszczam nawet, że kurs kryptologii i ekspozyturę [Biura Szyfrów] w Poznaniu zorganizowano właśnie w związku z pojawieniem się nowego rodzaju szyfru. Czy to z odczytanych depesz zaszyfrowanych systemem przestawienia podwójnego, czy też z innych źródeł, dość, że wiedziano, że jest to szyfr maszynowy. Wiedziano nawet, że maszyna, którą szyfrowano, nazywa się Enigma”.
Niespodziewanie dla wszystkich prace Rejewskiego zakończyły się sukcesem. Pod koniec grudnia 1932 r. młody kryptolog z Bydgoszczy ogłosił swoim zwierzchnikom, że udało mu się opracować matematyczną metodę łamania kodów maszyny szyfrującej Enigma. O doniosłości wyczynu Rejewskiego najlepiej świadczą słowa amerykańskiego historyka i kryptologa Davida Kahna, który w jednej ze swoich książek napisał:
„Jeśli 1000 kryptoanalityków, każdy dysponujący zdobytą Enigmą, sprawdzałoby po cztery klucze na minutę, pracując każdego dnia przez okrągłą dobę, a chciałoby sprawdzić wszystkie klucze, to ich praca trwałaby 1,8 miliarda lat”.
Rejewski dokonał tego w pojedynkę, pracując nad problemem zaledwie kilka tygodni.
Co warte podkreślenia, Rejewski złamał kod niemieckiej maszyny szyfrującej samodzielnie. Dopiero później dokooptowano do niego Różyckiego i Zygalskiego, aby wspólnie – z ogromnymi sukcesami zresztą – udoskonalali metodę deszyfrażu tego urządzenia. W celu ułatwienia sobie pracy młodzi kryptolodzy wykazali się wielką inwencją wymyślając różne urządzenia, które ułatwiały im prace związane z łamaniem szyfrów Enigmy.
Rejewski wymyślił m.in. cyklometr (urządzenie pomagające obliczać cykliczne permutacje Enigmy) oraz tzw. bombę, czyli urządzenie przyspieszające proces odnajdywania kluczy dziennych, według których nastawiono maszynę szyfrującą. Zygalski wymyślił system płacht perforowanych, za pomocą których można było ustalać kolejność wirników w Enigmie, z kolei Różycki opracował „metodę zegara”, która służyła do identyfikacji prawego, szybkiego wirnika maszyny. Dzięki tym „wynalazkom” prace nad deszyfrowaniem niemieckiej maszyny były znacznie łatwiejsze. W uznaniu tych zasług prezydent odznaczył kryptologów odznaczeniami państwowymi. W 1938 r. Rejewski otrzymał Złoty Krzyż Zasługi, a Różyckiemu i Zygalskiemu przyznano Srebrne Krzyże Zasługi.