It's probably a conflict between Java versions used by Flutter and Keytool. At least in my case it was.
1. Check Flutter JDK version
flutter doctor -v
It'll be something like Java version OpenJDK Runtime Environment (build 1.8...
1.8 means Java 8.
2. Check your computer's JDK version
java -version
In my case, it was Java 16, so I had to remove it (Instruction) and install OpenJDK 8.
3. Install OpenJDK
MacOS: https://formulae.brew.sh/formula/openjdk@8
Windows: Instruction
4. Update JAVA_HOME
MacOS:
/usr/libexec/java_home -V // this will show you jdk versions
export JAVA_HOME=`/usr/libexec/java_home -v 1.8` // specify your version here
Windows: Instruction
5. Re-create the keystore
Remove .jks file and create a new one: https://flutter.dev/docs/deployment/android#create-an-upload-keystore